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; }