POJ-3292 : Semi-prime H-numbers

問題概要

4*n+1で表される数をH-numberという。1*hでしか表せないH-numberをH-prime numberという。二つのH-prime numberの積で表されるH-numberをH-semi-prime numberという。[1..k](k<10^6)に含まれるH-semi-prime numberの個数を求める問題。

解法

篩をかける。計算量が読みにくいけどやってみると余裕で間に合う。

acceptされたコード

#include <cstdio>
using namespace std;

const int MAX_N = int(1e6)+1;

int accum[MAX_N + 1];
int divs[MAX_N + 1];

bool proc() {
	int x;
	scanf("%d", &x);
	if (x == 0) {
		return false;
	}
	printf("%d %d\n", x, accum[x]);
	return true;
}

void prepare() {
	divs[1] = 1;
	for (int i = 2; i <= MAX_N; ++i) {
		accum[i] = accum[i-1];
		if (i % 4 != 1) {
			divs[i] = 1;
			continue;
		}
		if (divs[i] == 0) {
			for (int j = 2*i; j <= MAX_N; j += i) {
				divs[j] = i;
			}
		}
		else if (divs[divs[i]] == 0 && divs[i/divs[i]] == 0) {
			++accum[i];
		}
	}
}

int main() {
	prepare();
	for (;proc();) ;

	return 0;
}