素数的判定

简介

素数又称质数，是指一个大于 \(1\) 的正整数，如果除了 \(1\) 和它本身以外，没有其他的约数，例如 \(2,3,5,7,3021377\) 等，反之就是合数。\(1\) 既不是素数也不是合数。

素数就像整数世界里的原子，整个整数世界都是由这些素数原子组成的，比如 \(15=3\times 5\) ，\(121=11\times 11\) 等等。有关素数的问题是数论研究的主要课题，我国著名数学家华罗庚教授及陈景润、王元研究员、潘承洞教授等对素论的研究都有重要贡献.

早在 2000 多年前的古希腊，伟大的数学家欧几里德就用反证法证明了：素数有无穷多个。在他的不朽名著《几何原本》第四卷命题 20 中是这样叙述的：预先给定几个素数，则有比他们更多的素数。他是这样证明的：设 \(a,b,c\) 是给定的素数，构造一个新的数 \(t=a\times b\times c+1\) ，则已有的素数 \(a,b,c\) 均不能整除 \(t\) ，所以要么 \(t\) 本身就是素数，此时 \(t\) 不等于 \(a,b,c\) 中任意一个数；要么 \(t\) 能被不同于 \(a,b,c\) 的某一个素数整除，因此必然存在一个素数力不同于已有的素数 \(a,b,c\) 。例如：\(2\times 3\times 5+1=31,3\times 5\times 7+1=106=2\times 53\) 。也就是说，有了 \(n\) 个素数，就可以构造出第 \(n+1\) 个素数，因此素数有无穷多个。

埃式筛法

对于数据范围比较大的情况下，需要找出所有素数，可以采用“筛选法”求出“素数表”。具体方法如下：

先将 \(2\sim N\) 之间的所有数写在纸上：\(2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,24,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40\cdots\)
在 \(2\) 的上面画一个圆圈，然后划去 \(2\) 的其他倍数；
第一个既未画圈又没有被划去的数是 \(3\)，将它画圈，再划去 \(3\) 的其他倍数；
现在既未画圈又没有被划去的第一个数是 \(5\) ，将它画圈，并划去 \(5\) 的其他倍数……
依次类推，一直到所有小于或等于 \(N\) 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 \(N\) 的素数。实现代码如下：

//埃式筛法
#include <bits/stdc++.h>
using namespace std;

bool isprime[10000000];

void sieve(int n)
{
    memset(isprime,true,sizeof(isprime));
    for(int i=2;i*i<=n;i++)
    {
        if(isprime[i])
        {
            for(int j=i*i;j<=n;j+=i)
                if(isprime[j])
                    isprime[j]=false;
        }
    }
} 

int main()
{
    int n;
    scanf("%d",&n);
    sieve(n);
    for(int i=2;i<=n;i++)
        if(isprime[i])
            printf("%d ",i);
    return 0;
}

欧拉筛法

仔细分析上述代码发现，这种方法会造成重复筛除合数，影响效率。比如 \(30\) ，在 \(i=2\) 的时候，\(k=2\times 15\) 筛了一次；在 \(i=5,k=5\times 6\) 的时候又筛了一次。所以，也就有了“快速线性筛法”。快速线性筛法没有冗余，不会重复筛除一个数，所以“几乎”是线性的，虽然从代码上分析，时间复杂度并不是 O(n) 。先看实现代码：

//欧拉筛法
#include <bits/stdc++.h>
using namespace std;

bool isprime[10000000];
int prime[5000000];

void Euler_sieve(int n)
{
    memset(isprime,true,sizeof(isprime));
    prime[0]=0;
    for(int i=2;i<=n;i++)
    {
        if(isprime[i])
            prime[++prime[0]]=i;
        for(int j=1;j<=prime[0] && i*prime[j]<=n;j++)
        {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)
                break;
        }
    }
} 

int main()
{
    int n;
    scanf("%d",&n);
    Euler_sieve(n);
    for(int i=1;i<=prime[0];i++)
        printf("%d ",prime[i]);
    return 0;
}

首先，先明确一个条件，任何合数都能表示成一系列素数的积。

如果 \(i\) 是素数的话，那简单，一个大的素数 \(i\) 乘以不大于 \(i\) 的素数，这样筛除的数跟之前的是不会重复的。筛出的数都是 \(n=p_1\times p_2\)的形式，\(p_1\) 和 \(p_2\) 不相等；
如果 \(i\) 是合数，此时 \(i\) 可以表示成递增素数相乘 \(i=p_1\times p_2\times \cdots \times p_n\) ，\(p_i\) 都是素数 \((2\leq i\leq n),p_i\leq p_j(i\leq j)\) ，\(p_1\) 是最小的系数。

根据上述代码，当 \(p_1==\text{prime}[j]\) 的时候，筛除就终止了，也就是说，只能筛出不大于 \(p_1\) 的质数\(\times i\) 。

我们可以直观地举个例子。\(i=2\times 3\times 5\) ，此时能筛除 \(2\times i\)，不能筛除 \(3\times i\) ，如果能筛除 \(3\times i\) 的话，当 \(i'=3\times 3\times 5\) 时，筛除 \(2\times i'\) 就和前面重复了。

当然，还有 2 个结论是可以证明的：

一个数不会被重复筛除；
合数肯定会被筛除。

参考资料：

林厚从《信息学奥赛之数学一本通》

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.