如何高效寻找素数 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：如何高效寻找素数

评论礼仪 见这里，违者直接拉黑。

[deepbreath373]

米青女少 ！

[Jebearssica]

只更新每个合数最小的素数可以优化到O(n)

[Maschinist-LZY]

比如 n = 25，i = 4 时算法会标记 4 × 2 = 8，4 × 3 = 12 等等数字，但是这两个数字已经被 i = 2 和 i = 3 的 2 × 4 和 3 × 4 标记了。 @labuladong 东哥，这里i=4, 4 = 2 x 2, 所以在i=2时4已经被标记为false，所以不会进入内层循环标记吧

[labuladong]

@Maschinist-LZY 嗯，你说得对，我大意了。把 i = 4 改成 i = 5 就没问题了，已修正~

[bert82503]

打卡，感谢楼主！

[nuo1nuo]

“首先，回想刚才判断一个数是否是素数的 isPrime 函数，由于因子的对称性，其中的 for 循环只需要遍历 [2,sqrt(n)] 就够了。这里也是类似的，我们外层的 for 循环也只需要遍历到 sqrt(n)”，没明白是怎么类似的？我个人觉得这里能优化成sqrt(n)的原因是内层循环的j被优化成从i^2开始，所以外层循环才可以被优化成sqrt(n)，而不是因为因子对称性

[yonggui-yan]

打卡。妙哉妙哉，排除法！