本文共 1031 字，大约阅读时间需要 3 分钟。
先筛出H-prime，在找出所有H-semi-prime。
询问的时候二分一下。
#include #include #include #include #include #include using namespace std;const long long maxn=1000001;long long v[maxn+10],cnt;long long ans[maxn+10],tot;bool f[maxn+10];bool p[maxn+10];void init(){ cnt=tot=0; memset(p,0,sizeof p); memset(f,0,sizeof f); for(long long i=5;i<=maxn;i=i+4) p[i]=1; for(long long i=5;i<=maxn;i=i+4) { if(p[i]==0) continue; v[cnt++]=i; for(long long j=5;;j=j+4) { long long tmp=j; if(i*tmp>maxn) break; while(1) { if(i*tmp>maxn) break; p[i*tmp]=0; tmp=tmp+j; } } } for(int i=0;i maxn) break; if(f[v[i]*v[j]]==1) continue; f[v[i]*v[j]]=1; ans[tot++]=v[i]*v[j]; } } sort(ans,ans+tot);}int main(){ init(); long long h; while(~scanf("%lld",&h)) { if(h==0) break; int pos=-1; int l=0,r=tot-1; while(l<=r) { int mid=(l+r)/2; if(ans[mid]<=h) pos=mid,l=mid+1; else r=mid-1; } printf("%lld %d\n",h,pos+1); } return 0;}
转载于:https://www.cnblogs.com/zufezzt/p/5385008.html