约 10 分钟
维护质数表 pr[]，对每个 i 用已知质数去筛。for(int i=2;i<=n;i++){ if(!notp[i]) pr[cnt++]=i; for(int j=0;j<cnt&&(long long)i*pr[j]<=n;j++){ notp[i*pr[j]]=1; if(i%pr[j]==0) break; } }。那句 break 是线性的关键。
pr[]
for(int i=2;i<=n;i++){ if(!notp[i]) pr[cnt++]=i; for(int j=0;j<cnt&&(long long)i*pr[j]<=n;j++){ notp[i*pr[j]]=1; if(i%pr[j]==0) break; } }
去掉 if(i%pr[j]==0) break; 会怎样？
if(i%pr[j]==0) break;
登录 后可看答案