UVa 11105 - Semi-prime H-numbers

// UVa 11105 - Semi-prime H-numbers

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;

vector<int> prime;
bool isprime[1000001];
int T[250001];

int main() {

	memset(isprime, true, sizeof(isprime));

	for (int i = 5; i <= 1000; i += 4) {
		if (isprime[i]) {
			prime.push_back(i);
			for (int j = i * i; j <= 1000000; j += i)
				isprime[j] = false;
		}
	}
	for (int i = 1001; i <= 1000000; i += 4) {
		if (isprime[i])
			prime.push_back(i);
	}

	T[0] = 0;
	for (int i = 1; i <= 250000; i++) {
		int h = (i << 2) + 1;
		bool found = false;
		for (int j = 0; j < prime.size() && prime[j] * prime[j] <= h; j++)
			if (h % prime[j] == 0 && isprime[h / prime[j]]) {
				found = true;
				break;
			}
		if (found)
			T[i] = T[i - 1] + 1;
		else
			T[i] = T[i - 1];
	}

	while (true) {
		int n;
		scanf("%d", &n);
		if (n == 0)
			break;
		int b = (n - 1) / 4;
		printf("%d %d\n", n, T[b]);
	}
	return 0;
}