POJ 3292 : Semi-prime H-numbers

概要

H={4N+1|Nは0以上の整数}とする．この時，Hの元xが1とxの組以外の積で表現できないものをHの素数と呼ぶことにする．h \in Hが与えられたとき，2つのHの素数の積で表すことができるh以下の数の個数を計算する．

解法

素数の列挙は篩を使っていい．
あとは，事前に数え上げる処理を行っておけばいい．

Hの素数の積は1通りでしか表せないと勘違いしていたので，なかなか通らなかった．
実際はそんなことはなく，9 * 111089 = 33 * 30297がその反例．

PKU 3292 Semi-prime H-numbers - 敗戦記 を見た．

int n;
ll prime[100000];
bool isnPrime[1000010];
int dp[1000010];
int h;
int main(){
    n = 0;
    for(int i = 5; i <= 1000001; i += 4) if(!isnPrime[i]){
        prime[n] = i;
        ++n;
        for(int j = i * 5; j <= 1000001; j += i * 4)
            isnPrime[j] = true;
    }
    for(int i = 0; i < n; ++i)for(int j = i; j < n && prime[i] * prime[j] <= 1000010; ++j){
        dp[prime[i] * prime[j]] = 1;
    }
    for(int i = 1; i <= 1000001; ++i){
        dp[i] += dp[i-1];
    }
    for(;;){
        scanf("%d", &h);
        if(h == 0) return 0;
        printf("%d %d\n", h, dp[h]);
    }
}