就是素数筛选，但是乘积重复的只算一个；
代码如下
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int maxn=1000005; int prime[maxn]; bool is_prime[maxn]; int ans[maxn]; void solve() { int p=0; memset(is_prime,true,sizeof(is_prime)); for(int i=5;i<maxn;i+=4){ if(is_prime[i]){ prime[p++]=i; for(int j=2*i;j<maxn;j+=i) { if((j-1)%4==0) is_prime[j]=false; } } } for(int i=0;i<p;i++){ if(prime[i]>10000) break; for(int j=i;j<p;j++){ int temp=prime[i]*prime[j]; if(temp>maxn) break; ans[temp]=1; } } for(int i=0;i<maxn;i++) ans[i]+=ans[i-1]; } int main() { solve(); int h; while(~scanf("%d",&h)){ if(h==0) break; else printf("%d %d\n",h,ans[h]); } }