质数筛算法详解

· · 个人记录

今天给大家讲解质数筛这个算法。

更好的阅读体验

在信息竞赛中，我们总是会遇到很多判断质数的题目，那么在这里就由我来给大家讲解一下质数筛算法（这里所有讲的算法都是基于筛出从 1 到 n 之间的素数的算法）。

1.普通筛法

最普通的筛法，也就是将前 n 个正整数一个一个来判断是否为素数，并且在判断素数的时候要从 2 枚举到 这个数-1 来判断。

关键代码

for(int i=1;i<=n;++i)//枚举1到n
{
    bool flg=0;
    for(int j=2;j<i;++j)//枚举2到i
    {
        if(i%j==0)//如果i%j=0,也就是i已经不为素数了
        {
            flg=1;//打上标记
            break;//跳出循环，不用再枚举了
        }
    }
    if(flg==0)//如果没有被打上标记
    prime[i]=1;//prime来标记这个数是否为素数。
}

这样的时间复杂度最劣近似 O(n^2)。

2.普通筛法的优化

学过奥数的朋友们可能会发现，在判断素数的时候，不一定需要枚举到 i-1 只需要枚举到 \sqrt{i} 就可以判断出来了。

关键代码

for(int i=1;i<=n;++i)//枚举1到n
{
    bool flg=0;
    for(int j=2;j*j<=i;++j)//枚举2到i
    {
        if(i%j==0)//如果i%j=0,也就是i已经不为素数了
        {
            flg=1;//打上标记
            break;//跳出循环，不用再枚举了
        }
    }
    if(flg==0)//如果没有被打上标记
    prime[i]=1;//prime来标记这个数是否为素数。
}

这样的时间复杂度最劣近似 O(n\sqrt{n})。

3.暴力筛

我们发现，上面两种筛法会筛到许多没有意义的数，所以我们必须换一种思想方式。

暴力筛，就是先将 prime 数组全部赋值为 1。(记得将 prime_1 赋值为 0 )。 仍然是要从 1 枚举到 n 。我们先假设当前枚举到了 i 。

如果 prime_i=1 也就是 i 为质数，则我们可以知道 i 的倍数均为合数，所以我们就将 prime_{i\times k<n ,k>=2} 赋值为 0 。

最终筛完之后，如果 prime_i=1 , i 就是质数。

关键代码

memset(prime,1,sizeof(prime));
priem[1]=0;
for(int i=2;i<=n;++i)
{
    if(prime[i])
    {
        for(int j=2;j*i<=n;++j)
        prime[i*j]=0;
    }
}

显然，该程序一共会执行 \sum\limits_{i=2}^n \dfrac{n}{i}\approx \lim\limits _{n \to \infty}\sum\limits_{i=2}^n \dfrac{n}{i}= n \ln n 次。

4.埃氏筛

埃氏筛是基于暴力筛法的一种优化。

我们发现，对于暴力筛中小于 i\times i 的数，假设其为 i \times j，则必然有 j<i，所以这个数已经被 j 筛掉了，不用再去考虑，所以对于第二重循环，我们可以从 i，一直枚举到边界。

memset(prime,1,sizeof(prime));
priem[1]=0;
for(int i=2;i<=n;++i)
{
    if(prime[i])
    {
        for(int j=i;j*i<=n;++j)
        prime[i*j]=0;
    }
}

对于第一重循环，可以只枚举到 \sqrt n，因为在这个范围以内就可以筛掉所有的合数。

对于时间复杂度，因蒟蒻能力有限，不会证明，只给出具体时间复杂度是 n\ln \ln n。

5.欧拉筛(线性筛)

我们发现，埃氏筛已经很快了，但是还是有所不足。

因为在埃氏筛中，有很多数有可能被筛到很多次（例如 6 , 他就被 2 和 3 分别筛了一次）。 所以在欧拉筛中，我们就是在这个问题上面做了优化，使得所有合数只被筛了一次。

首先，我们定义 st_i 数组表示 i 是否为质数，primes_i 储存已经找到的所有质数，cnt 储存当前一共找到了多少质数。

如果当前已经枚举到了 i 。如果 st_i=1 ，也就是 i 为素数。则 primes_{cnt+1}=i。

然后我们每一次枚举都要做这个循环: 枚举 j 从 1 到 cnt。st_{primes_j\times i}=0（因为 primes_j 为素数，i 就表示这个素数的多少倍，要把他筛掉）。

注意，接下来是重点！ 如果 i\mod primes_j=0，跳出第二层循环

为什么呢，我们可以这样想。

我们假设当前枚举到的 i 的最小质因子为 primes_k。

则在枚举 1 \to k-1 时，可以保证 primes_j<primes_k。（primes 数组一定递增。）所以 i\times primes_j 的最小质因子一定是 primes_j。

当枚举到了 k 时，可以发现，当前的 primes_k\times i 的最小质因子一定是 primes_k，只不过多含了几个 primes_k。

最后枚举 k 以后的数时，我们可以发现当前 primes_j>primes_k，这个素数并没有被他的最小质因子筛掉，所以 break。

关键代码

memset(st,0,sizeof(st));
st[1]=0;
for(i=2;i<=n;i++)
{
    if(st[i])
    primes[cnt++]=i;
    for(j=0;primes[j]*i<=n&&j<=cnt;j++)
    {
        st[primes[j]*i]=0;
        if(i%primes[j]==0)
        break;
    }
}

关于正确性

你可能会问，为啥他一定能把所有的素数筛到？

假设有质数没有筛到，其中一个为 z。

设其最小质因子为 primes_l。

则当我们枚举到 z/primes_l 时，他的循环边界条件一定能枚举到 l，所以如果他没有枚举到一定是中间 break 了。

假设使他 break 的质数为 primes_x 且 x<l。则 z/primes_l \mod primes_x=0 且 primes_x<primes_l。

而这样的话，z 的最小质因子就是 primes_x 而不是 primes_L，所以矛盾。

所以这样的方法一定是正确的，且一定使用到的最小质因子来筛。

这样的时间复杂度为 O(n)。