判断素数的常见方法

文章目录

• ​一、素数的定义
• 二、素数测试：暴力法
• 三、暴力法的优化：试除法
• 四、素数生成：埃氏筛
• 五、埃氏筛的优化：欧拉筛
• • 欧拉筛的原理
  • 欧拉筛代码示例(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 < n; ++i)
    { // 遍历大于1且小于根号n的整数
        if (n % i == 0)
        { // 如果n可以被某数整除，则为合数
            return false;
        }
    }
    return true; // 遍历结束，则为素数
}

优点：

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

缺点：

时间复杂度为

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 <= n / i; ++i)
    { // 遍历大于1且小于根号n的整数
        if (n % i == 0)
        { // 如果n可以被某数整除，则为合数
            return false;
        }
    }
    return true; // 遍历结束，则为素数
}

遍历2到

n

\sqrt{n}

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

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

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

如果要判断从 1 到

n

n

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

O

(

n

n

)

O(n\sqrt{n})

O(nn
​)，可以看出算法还是十分缓慢的。

四、素数生成：埃氏筛

在实际应用中，如果我们要追求更高效率，通常会使用预先建立数组来存储从 1 至

n

n

n 的所有素数，方便多次查找。此时素数生成(Generation of primes)的算法就尤为重要。

埃拉托斯特尼筛法(Sieve of Eratosthenes)，简称埃氏筛，也称素数筛，是简单且历史悠久的筛法，用来找出一定范围内所有素数。

埃氏筛的基本思路：给定要筛数值的范围

n

n

n，从2开始，将每个素数的各倍数标记成合数。如果一个数没有被之前的数标记，那它一定是素数。

同理，我们只需要遍历 2 至

n

\sqrt{n}

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

)

O(n\log\log n)

O(nloglogn)，尽管已经十分优秀了，但仍然存在进步的空间。

在埃氏筛算法中，存在很多被重复筛除的情况，例如12会被2和3重复筛除，30会被2, 3和5重复筛除。

因此在埃氏筛的基础上，出现了有着线性时间复杂度的算法：欧拉筛。

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

欧拉筛的原理

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

• 欧拉筛不再只筛除素数的倍数，合数的倍数也会进行标记。
• 欧拉筛必须要借助已经筛出的素数来完成，因此需要记录已筛出素数。
• 欧拉筛只会筛除

  i

  i

  i 的素数倍数，同时这个素数小于等于

  i

  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

  x

  x，我们可以提出它的最小质因子

  p

  p

  p，得到

  x

  =

  p

  a

  x = pa

  x=pa。显然

  a

  <

  x

  a < x

  a<x，同时不难想到

  a

  a

  a 的最小质因子一定大于等于

  p

  p

  p。

  在算法运行过程中，由于

  a

  <

  x

  a < x

  a<x，

  a

  a

  a 会先被外层循环所遍历，这时算法枚举所有质数，由于

  a

  a

  a 的最小质因子大于等于

  p

  p

  p，因此

  p

  a

  =

  x

  pa = x

  pa=x 一定会被筛除，证毕。

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

观察欧拉筛的代码，可以得出外层循环for(int i=2; i<=n; ++i)的时间复杂度是

O

(

n

)

O(n)

O(n)，而对于内层循环for(int j=0; j<cnt && i * prime[j] <= n; ++j)的时间复杂度，我们很难直接判断。

从另一个角度入手，我们可以证明isPrime[i * primes[j]] = false;在整个算法中运行了最多

n

n

n 次，来保证总体时间复杂度仍是

O

(

n

)

O(n)

O(n)。这样一来，我们需要证明了每一个自然数最多会被筛除一次。

对于任意合数

x

x

x，我们可以提出它的最小质因子

p

1

p_1

p1​，得到

x

=

p

1

a

x = p_1a

x=p1​a，根据我们对欧拉筛正确性的证明，

x

x

x 一定会在

a

a

a 被遍历时筛掉。那除了

x

=

p

1

a

x = p_1a

x=p1​a，会不会有其他可以筛除

x

x

x 的情况呢？

假设合数

x

x

x 还可以提出其他质数

p

2

p_2

p2​，得到

x

=

p

2

b

x = p_2b

x=p2​b。这里

p

2

p_2

p2​ 不是最小质因子，所以

p

1

<

p

2

p_1 < p_2

p1​<p2​。由于

x

=

p

1

a

=

p

2

b

x = p_1a = p_2b

x=p1​a=p2​b，我们不难证明

b

b

b 的最小质因子其实就是

p

1

p_1

p1​。那么当算法遍历到

b

b

b 时，

b

b

b 会因b % p1 == 0给提前终止，无法筛除

p

2

b

=

x

p_2b = x

p2​b=x。因此，除

x

=

p

1

a

x = p_1a

x=p1​a 以外的所有组合都不会筛除

x

x

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