对于这道题,可以用埃筛统计出质因子的同时,用并查集合并同一帮派即可。
需要注意的是,这道题不是纯正的筛质数,埃筛的第二重循环不能从 i*i 开始,只能老老实实从 i 开始循环。
const int mn=5e4+10; const int mm=5e4+10; const int mod=1e9+7; const int inf=0x3f3f3f3f; const int fni=0xc0c0c0c0; int a,b,k; bool v[mn],o[mn]; int p[mn],tot; int f[mn]; int find(int x){return f[x]==x?x:f[x]=find(f[x]);} void merge(int a,int b){f[find(b)]=find(a);} inline void read_init(){ a=read<int>();b=read<int>();k=read<int>(); for(int i=1;i<=b;i++) f[i]=i; for(int i=2;i<=b;i++){ if(v[i])continue; p[++tot]=i; for(ll j=i;j<=b;j+=i){ v[j]=i; if(i>=k && j>=a && j<=b) merge(j,(a-1)/i*i+i); } } } int main(){ // freopen("merge.in","r",stdin); // freopen("merge.out","w",stdout); read_init(); int sum=0; for(int i=a;i<=b;i++) if(!o[find(i)]){ o[find(i)]=1; sum++; } write(sum,1); return 0; }