c++ - 找到质数的最佳方法是什么？

Question

<分区>

Answer 1

在寻找素数时，Sieve of Eratosthenes和 Sieve of Atkin是两种可能的解决方案。 Eratosthenes 筛法的复杂度为 O((n log n)(log log n))。阿特金筛的复杂度为 O(N/log log n)。

如果你有一个数字，你想知道它是否是质数，这称为执行 primality test .天真的方法是检查从 2 到 sqrt(n) 的所有数字 m 并验证 n % m 不为 0。如果你想稍微扩展一下，你可以扔掉所有偶数(2 除外)。对于这种朴素的方法还有一些其他的改进，可能会提高性能，以及其他更高级的技术。