「数学::质数」埃氏筛|欧拉筛（埃拉托斯特尼筛法|线性筛法）/ LeetCode 204（C++）

目录

概述

1.埃氏筛

思路

复杂度

Code

2.欧拉筛（线性筛）

思路

复杂度

Code

总结

概述

上一节我们介绍了对判断一个数是否为质数的方法：「数学::质数」试除法 / Luogu P5736（C++）

那如果我们期望输出一个范围内的所有质数，使用试除法的时间复杂度是n√n，怎么办呢？

LeetCode 204：

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

1.埃氏筛

思路

质数的倍数一定不是质数；反之，一个数不是任何比它小的质数的倍数，它一定是质数。

定义bool not_prim数组，not_prim[i]值为真，表示i不是质数；值为假，表示i是质数。

从i=2遍历到n:

①如果not_prim[i]=false，表示它不是之前的任何一个数的倍数，也就是没有被筛掉，则它是质数，加入答案，再枚举它的倍数，将之筛掉。

②如果not_prim[i]=true，表示它不是质数，直接枚举他的倍数，将之筛掉。

在枚举i的倍数依次筛掉时，我们可以直接从i^2开始枚举，因为i到i^2之间的数已经被i前面的数筛过了。下附证明：

设有质数b，则kb为其不大于b^2的整数倍(k=2,3...b-1)，即: 2b<=kb<=(b-1)*b。

注意到，k可表示为小于b的某一质数a的t倍。即：k=at(t>=1)。

则kb=atb，令tb=u，有kb=ua，其中u为a的某一倍数，因此筛a的倍数时已经筛掉了kb。

*注意*：我们只计算n以内的质数，因此ua=kb<n。

复杂度

时间复杂度: O(nlog(logn)) 

空间复杂度: O(n)

时间复杂度证明详见OI Wikihttps://oi-wiki.org/math/number-theory/sieve/，此处略去不表

Code

const int N=5e6+1;
class Solution {
    bool not_prim[N]={1,1,0};
    vector<int>prim;
public:
    int countPrimes(int n) {
        for(int i=2;i<n;i++){
            if(!not_prim[i])prim.push_back(i);
            for(long long j=1LL*i*i;j<n;j+=i)//1ll是为了防爆int
               not_prim[j]=true;
        }
        return prim.size();
    }
};

2.欧拉筛（线性筛）

思路

埃氏筛进行了很多次无用的筛数，比如说枚举2的倍数后已经不必再枚举4的倍数了。

欧拉想了一个方法：限制每个数的枚举上限。

比如说限制2的枚举倍数，使得4的倍数不会被2全部枚举一遍，这样每个数都只枚举几次，使得时间复杂度达到线性级别，故又称线性筛。

 bool not_prim数组和筛倍数的策略仍然保持不变，但是我们多了两条原则：

①：i不仅用于枚举[2,n)的所有数是否为质数，也作为倍数用来筛数。

这是指双层for循环，外层i枚举所有数，内层j枚举所有已获得的质数，令not_prim[prim[j]*i]=true;

*注意*：埃氏筛中，i枚举所有数，j枚举倍数；欧拉筛中，i枚举所有数，同时作为倍数，j则枚举已知质数。

②：i%prim[j]==0时停止继续枚举j，保证每个合数都被他的最小质因子筛掉。

我们重点讲一下这个原则：

考虑：

i会枚举[2,n)之间的所有数，那i自然就可以表示倍数k，那么对于每个i都枚举已知的prim[j]进行筛倍数是合理又合法的。

遍历到i时，已经知晓了[2,i]之间的所有数是否是质数。同时可以确定的是，prim[j]必定是小于等于i的质数，且其中元素升序排序。

在我们筛掉i*prim[j]=x后，如果i%prim[j]==0，即i=k*prim[j]，就不必再筛i*prim[j+1]=y了，因为i*prim[j+1]可以被分解为k*prim[j]*prim[j+1]，即k*prim[j+1]*prim[j]，其中k*prim[j+1]将是后续的某个i值。

如i=6是prime[1]=3的倍数，我们在筛完i*prim[1]=18之后，不必再筛i*prim[2]=30了，因为当i=10时，30会被i*prim[1]筛掉。

      j  0 1 2 3 
prime[j] 2 3 5 7 

复杂度

时间复杂度: O(n) 

空间复杂度: O(n)

Code

const int N=5e6+1;
class Solution {
    bool not_prim[N]={0};
    vector<int>prim;
public:
    int countPrimes(int n) {
        for(int i=2;i<n;i++){
            if(!not_prim[i])prim.push_back(i);
            for(int j=0;prim[j]*i<n;j++){
                not_prim[prim[j]*i]=true;
                if(!(i%prim[j]))break;
            }
        }
        return prim.size();
    }
};

*注意*：使用vector存储所有质数是为了减小空间复杂度，如果你希望达到欧拉筛的最优性能，可以开一个巨大的定长数组存储质数。

总结

埃氏筛和欧拉筛是两种几乎跑在线性时间的质数算法，他们在处理大量数据时的性能极其优异，我们尤其希望你理解了欧拉筛的两条原则，这有助于培养线性递推的能力。