行业知识
判断素数的常见方法
文章目录
- 一、素数的定义
- 二、素数测试：暴力法
- 三、暴力法的优化：试除法
- 四、素数生成：埃氏筛
- 五、埃氏筛的优化：欧拉筛
- 欧拉筛的原理
- 欧拉筛代码示例(C++)
- 欧拉筛的正确性证明
- 欧拉筛的线性时间复杂度证明
- ��、参考资料
一、素数的定义
素数(Prime number)，又称质数，是指在大于1的自然数中，除了1和它自身外，不能被任何其他自然数整除的数叫做质数；否则称为合数。
值得注意的是，0 与 1 既不是素数，也不是合数。
二、素数测试：暴力法
素性测试(Primality test)，或素数判定，是检验一个给定的整数是否为素数的测试。
判断 n n n 是否为素数时，最简单的方式就是暴力法(Brute Force)：遍历的所有大于 1 且小于 n n n 的整数，判断 n n n 是否可以被这些数整除，如果不存在可以整除的数，则为素数；否则为合数。
bool isPrime(int n){ for (int i = 2; i 优点： 简单易懂，完全利用了素数的定义。 缺点： 时间复杂度为 O ( n ) O(n) O(n), 当需要判断大量的数时十分缓慢。 如果需要判断从 1 到 n n n 的的每一个数，则总体时间复杂度为 O ( n 2 ) O(n^2) O(n2).三、暴力法的优化：试除法
试除法(Trial Division)中的思想告诉我们，遍历到 n \sqrt{n} n 即可判断 n n n 是否为素数。
可以通过反证法证明：
假设遍历到 n \sqrt{n} n 仍然无法判断 n n n 是否为素数，则存在自然数 a , b a,b a,b 使得 n = a ⋅ b n = a\cdot b n=a⋅b，同时 a a a 与 b b b 其中之一大于 n \sqrt{n} n 。
如果 a a a 与 b b b 其中之一大于 n \sqrt{n} n ，而另一个小于 n \sqrt{n} n ，则较小数会在遍历到 n \sqrt{n} n 前被遍历到，与假设矛盾。
如果 a a a 与 b b b 皆大于 n \sqrt{n} n ，则 a ⋅ b > n a\cdot b > n a⋅b>n，与假设矛盾。
将这一重要性质应用到我们的算法中，可以减少需要遍历的整数数量。在新的算法中，时间复杂度降到了 O ( n ) O(\sqrt{n}) O(n )
bool isPrime(int n){ for (int i = 2; i // 遍历大于1且小于根号n的整数 if (n % i == 0) { // 如果n可以被某数整除，则为合数 return false; } } return true; // 遍历结束，则为素数} // 埃氏筛 memset(isPrime, true, sizeof(isPrime)); // 先将所有的数标记为素数 isPrime[0] = false; isPrime[1] = false; // 0，1皆不是素数 for (int i = 2; i // 遍历2到根号n的间的所有整数 if (isPrime[i]) { // 如果i为素数，则将它的所有倍数标记 for (int j = i * i; j // 小于i*i的 i的倍数 已经被之前的素数标记过了，因此可以跳过 isPrime[j] = false; } } }} memset(isPrime, true, sizeof(isPrime)); // 先将所有的数标记为素数 isPrime[0] = false; isPrime[1] = false; // 0，1皆不是素数 for (int i = 2; i // 遍历2到n间的所有整数 if (isPrime[i]) primes[cnt++] = i; // i是素数，那么将i添加到已筛出的素数中，cnt++ for (int j = 0; j
