判断素数的常见方法-Toy模板网

这篇具有很好参考价值的文章主要介绍了判断素数的常见方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、素数的定义

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

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

二、素数测试：暴力法

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

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

优点：

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

缺点：

时间复杂度为

O (n)

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

如果需要判断从 1 到

n

的的每一个数，则总体时间复杂度为

O(n^2)

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

试除法(Trial Division)中的思想告诉我们，遍历到 $\sqrt{n}$ 即可判断 $n$ 是否为素数。

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

将这一重要性质应用到我们的算法中，可以减少需要遍历的整数数量。在新的算法中，时间复杂度降到了 $O(\sqrt{n})$

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

遍历2到

\sqrt{n}

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

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

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

如果要判断从 1 到 $n$ 的的每一个数，则总体时间复杂度为 $O(n\sqrt{n})$ ，可以看出算法还是十分缓慢的。

四、素数生成：埃氏筛

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

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

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;
            }
        }
    }
}

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

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

欧拉筛的原理

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

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

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

欧拉筛代码示例(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]，这个数由两个数相乘，因此一定不是素数，所以素数不会被筛除，证毕。
所有合数都会被筛除：
对于任意合数 $x$ ，我们可以提出它的最小质因子 $p$ ，得到 $x = p a$ 。显然 $a < x$ ，同时不难想到 $a$ 的最小质因子一定大于等于 $p$ 。
在算法运行过程中，由于 $a < x$ ， $a$ 会先被外层循环所遍历，这时算法枚举所有质数，由于 $a$ 的最小质因子大于等于 $p$ ，因此 $p a = x$ 一定会被筛除，证毕。

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

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

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

六、参考资料

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文章来源地址https://www.toymoban.com/news/detail-715778.html

到了这里，关于判断素数的常见方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！