PKU 3292 Semi-prime H-numbers
http://poj.org/problem?id=3292
4の倍数+1の形で表される数のうち、1とその数以外に、4の倍数+1で表される約数を持たないものをH素数と呼ぶ。
このとき、ある数字以下のもので、ちょうど二つのH素数の積で表される数の個数を答えろというような問題。
ふるいと同じように生成して、かけて合成数を除外して、足しました。
bool pr[1000001]; int npr[1000100]; int pos; int dp[1000011]; bool co[1000011]; main(){ for(int i=5;i<=1000010;i+=4){ if(pr[i])continue; npr[pos++]=i; for(int j=i*5;j<=1000010;j+=i*4)pr[j]=true; } rep(i,pos){ rep(j,i+1){ if(npr[i]*npr[j]>1000010)break; co[npr[i]*npr[j]]=true; } } rep(i,1000010) dp[i+1]=dp[i]+co[i+1]; int n; while(scanf("%d",&n),n)printf("%d %d\n",n,dp[n]); }