约 8 分钟
i 的倍数里比 i×i 小的那些(如 2i、3i…)在处理更小质数时已被划掉,所以内层可从 i×i 开始:for(int j=i*i;j<=n;j+=i),外层只需 i*i<=n。这样能明显减少重复标记。
for(int j=i*i;j<=n;j+=i)
i*i<=n
i=5 时,内层从哪个数开始标记?
登录 后可看答案