判断素数的常见方法

文章目录

一、素数的定义
二、素数测试：暴力法
三、暴力法的优化：试除法
四、素数生成：埃氏筛
五、埃氏筛的优化：欧拉筛
- 欧拉筛的原理
- 欧拉筛代码示例(C++)
- 欧拉筛的正确性证明
- 欧拉筛的线性时间复杂度证明
六、参考资料

一、素数的定义

素数(Prime number)，又称质数，是指在大于1的自然数中，除了1和它自身外，不能被任何其他自然数整除的数叫做质数；否则称为合数。

值得注意的是，0 与 1 既不是素数，也不是合数。

二、素数测试：暴力法

素性测试(Primality test)，或素数判定，是检验一个给定的整数是否为素数的测试。
判断判断素数的常见方法是否为素数时，最简单的方式就是暴力法(Brute Force)：遍历的所有大于 1 且小于的整数，判断是否可以被这些数整除，如果不存在可以整除的数，则为素数；否则为合数。

bool isPrime(int n)
{
    for (int i = 2; i < n; ++i)
    { // 遍历大于1且小于根号n的整数
        if (n % i == 0)
        { // 如果n可以被某数整除，则为合数
            return false;
        }
    }
    return true; // 遍历结束，则为素数
}

优点：

简单易懂，完全利用了素数的定义。

缺点：

时间复杂度为

, 当需要判断大量的数时十分缓慢。

如果需要判断从 1 到判断素数的常见方法

的的每一个数，则总体时间复杂度为判断素数的常见方法

三、暴力法的优化：试除法

试除法(Trial Division)中的思想告诉我们，遍历到判断素数的常见方法即可判断是否为素数。

可以通过反证法证明：
假设遍历到仍然无法判断是否为素数，则存在自然数使得，同时与其中之一大于。
如果与其中之一大于，而另一个小于，则较小数会在遍历到前被遍历到，与假设矛盾。
如果与皆大于，则，与假设矛盾。

将这一重要性质应用到我们的算法中，可以减少需要遍历的整数数量。在新的算法中，时间复杂度降到了判断素数的常见方法

bool isPrime(int n)
{
    for (int i = 2; i <= n / i; ++i)
    { // 遍历大于1且小于根号n的整数
        if (n % i == 0)
        { // 如果n可以被某数整除，则为合数
            return false;
        }
    }
    return true; // 遍历结束，则为素数
}

遍历2到

的整数时，建议使用 i <= n/i，而非 i <= sqrt(n)或 i * i <= n

i <= sqrt(n)会多次调用 <math.h>库中的 sqrt()函数，拖慢运行速度。

i * i <= n则会有数值溢出的风险。

如果要判断从 1 到判断素数的常见方法的的每一个数，则总体时间复杂度为，可以看出算法还是十分缓慢的。

四、素数生成：埃氏筛

在实际应用中，如果我们要追求更高效率，通常会使用预先建立数组来存储从 1 至判断素数的常见方法的所有素数，方便多次查找。此时素数生成(Generation of primes)的算法就尤为重要。
埃拉托斯特尼筛法(Sieve of Eratosthenes)，简称埃氏筛，也称素数筛，是简单且历史悠久的筛法，用来找出一定范围内所有素数。

埃氏筛的基本思路：给定要筛数值的范围判断素数的常见方法，从2开始，将每个素数的各倍数标记成合数。如果一个数没有被之前的数标记，那它一定是素数。
同理，我们只需要遍历 2 至的所有素数即可生成素数表。
埃氏筛找出范围[2,120]的素数

const int MAXSIZE=1e7; //定义空间大小10^7
bool isPrime[MAXSIZE+1]; //素数表，如果isPrime[i]为true，则i为素数；否则为合数

void Eratosthenes_Sieve(int n)
{                                           // 埃氏筛
    memset(isPrime, true, sizeof(isPrime)); // 先将所有的数标记为素数
    isPrime[0] = false;
    isPrime[1] = false; // 0，1皆不是素数

    for (int i = 2; i <= n / i; ++i)
    { // 遍历2到根号n的间的所有整数
        if (isPrime[i])
        { // 如果i为素数，则将它的所有倍数标记
            for (int j = i * i; j <= n; j += i)
            { // 小于i*i的 i的倍数 已经被之前的素数标记过了，因此可以跳过
                isPrime[j] = false;
            }
        }
    }
}

此算法的时间复杂度为判断素数的常见方法，尽管已经十分优秀了，但仍然存在进步的空间。
在埃氏筛算法中，存在很多被重复筛除的情况，例如12会被2和3重复筛除，30会被2, 3和5重复筛除。
因此在埃氏筛的基础上，出现了有着线性时间复杂度的算法：欧拉筛。

五、埃氏筛的优化：欧拉筛

欧拉筛的原理

欧拉筛(Sieve of Euler)沿用了埃氏筛的思路，在遍历中将素数的倍数筛除。然而与埃氏筛不同的是：

欧拉筛不再只筛除素数的倍数，合数的倍数也会进行标记。
欧拉筛必须要借助已经筛出的素数来完成，因此需要记录已筛出素数。
欧拉筛只会筛除的素数倍数，同时这个素数小于等于的最小质因子。

上述三条看起来十分莫名其妙，因此下面用一份代码来帮助理解。

欧拉筛代码示例(C++)

const int MAXSIZE=1e7; //定义空间大小10^7
bool isPrime[MAXSIZE+1]; //素数表，如果isPrime[i]为true，则i为素数；否则为合数
int primes[MAXSIZE]; //已筛出的素数， 素数会按从小到大的顺序不断加入此数组
int cnt = 0; //已筛出的素数的总数

void Euler_Sieve(int n)
{
    memset(isPrime, true, sizeof(isPrime)); // 先将所有的数标记为素数
    isPrime[0] = false;
    isPrime[1] = false; // 0，1皆不是素数

    for (int i = 2; i <= n; ++i)
    { // 遍历2到n间的所有整数
        if (isPrime[i])
            primes[cnt++] = i; // i是素数，那么将i添加到已筛出的素数中，cnt++
        for (int j = 0; j < cnt && i * primes[j] <= n; ++j)
        {                                   // 枚举所有已筛出的质数
            isPrime[i * primes[j]] = false; // 标记i的素数倍数为合数
            if (i % primes[j] == 0)
                break; // 如果i可以被素数prime[j]整除，跳出循环
        }
    }
}

使用i筛除后面的数时，枚举已经筛出来的素数 prime[j]，标记i * prime[j]为合数，当i是prime[j]的倍数时，停止枚举并进行下一轮i+1的筛除。在这一过程中，if(i % prime[j] == 0) break;是整个欧拉筛线性时间复杂度的关键点，也是最难理解的部分。

通俗地来讲，如果想要保持线性时间复杂度，就要保证每一个整数都只被标记过一次。如果我们无视了if(i % prime[j] == 0) break;继续进行筛除会发生什么呢？不难想象，算法会筛除掉i * prime[j+1]、i * prime[j+2]、i * prime[j+3]等更多倍数。
然而，这些后续的倍数都必然会被重复筛除，以i * prime[j+1]为例，我们先假设i = a * prime[j]，这样一来i * prime[j+1]就可以写成a * prime[j] * prime[j+1] = (a * prime[j+1]) * prime[j]。
可以看出，i * prime[j+1]一定会被a * prime[j+1]重复筛除，之后的每一个倍数也都有着同样的情况。因此，为了避免后续的重复筛除，我们应该在i % prime[j] == 0时跳出循环。

以上只是我个人的简单理解，严谨的证明下文将给出详细过程。

欧拉筛的正确性证明

素数不会被筛除：
整个过程中我们只筛除了i * prime[j]，这个数由两个数相乘，因此一定不是素数，所以素数不会被筛除，证毕。
所有合数都会被筛除：
对于任意合数，我们可以提出它的最小质因子，得到。显然，同时不难想到的最小质因子一定大于等于。
在算法运行过程中，由于，会先被外层循环所遍历，这时算法枚举所有质数，由于的最小质因子大于等于，因此一定会被筛除，证毕。

欧拉筛的线性时间复杂度证明

观察欧拉筛的代码，可以得出外层循环for(int i=2; i<=n; ++i)的时间复杂度是判断素数的常见方法，而对于内层循环for(int j=0; j<cnt && i * prime[j] <= n; ++j)的时间复杂度，我们很难直接判断。
从另一个角度入手，我们可以证明isPrime[i * primes[j]] = false;在整个算法中运行了最多次，来保证总体时间复杂度仍是判断素数的常见方法。这样一来，我们需要证明了每一个自然数最多会被筛除一次。

对于任意合数判断素数的常见方法，我们可以提出它的最小质因子，得到，根据我们对欧拉筛正确性的证明，一定会在被遍历时筛掉。那除了，会不会有其他可以筛除的情况呢？
假设合数还可以提出其他质数，得到。这里不是最小质因子，所以判断素数的常见方法。由于，我们不难证明的最小质因子其实就是。那么当算法遍历到时，会因b % p1 == 0给提前终止，无法筛除。因此，除以外的所有组合都不会筛除，证毕。

六、参考资料

https://blog.csdn.net/qaqwqaqwq/article/details/123587336
https://blog.csdn.net/Gold_Medal/article/details/107732553

素数研究是数论(Number Theory)的重要组成部分，上述提到的试除法，埃氏筛和欧拉筛都是其冰山一角，可访问维基百科了解更多：

素数测试：https://zh.wikipedia.org/wiki/素数测试
Primality Test: https://en.wikipedia.org/wiki/Primality_test
Generation of primes: https://en.wikipedia.org/wiki/Generation_of_primes

文章出处登录后可见！

已经登录？立即刷新