埃氏筛·优化

8 分钟

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

小纸条

i=5 时,内层从哪个数开始标记?

登录 后可看答案

埃氏筛·优化 · 算法进阶 · op599 课程