普通筛法

原理

由于合数必是某个数的倍数，所以可以用未去掉的数将其所有的倍数去掉，剩下的未被去掉的数即为质数。

来自知乎的例子：

代码

时间复杂度：\(O(nlogn)\)

#include <bits/stdc++.h>
#define N 1000010

int cnt;
bool st[N];
int primes[N];

void get_primes(int n) {
    
     for(int i=2;i<=n;i++){
         
        if(!st[i]) primes[cnt++]=i;//把素数存起来
        
        for(int j=i;j<=n;j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数
            st[j]=true;
        }
    }
    return ;
}

int main() {
    int n;
    std::cin >> n;
    
    get_primes(n);

    return 0;
}

埃氏筛法

原理

由算数基本定理，某合数可以表示为多个质因数的乘积，所以只需要质数也可以达到朴素筛法的效果。

则只需要用质数来去掉合数，而不需要用到合数来去除。

代码

时间复杂度：\(O(nloglogn)\)

#include <bits/stdc++.h>
#define N 1000010

int cnt;
bool st[N];
int primes[N];

void get_primes(int n) {
    for (int i = 2 ; i <= n ; i ++ ) {
        if(!st[i]) {
            primes[cnt ++ ] = i;
            for (int j = i + i ; j <= n ; j += i) {
                st[j] = true;
            }
        }
    }
    return ;
}

int main() {
    int n;
    std::cin >> n;
    
    get_primes(n);
    
    return 0;
}

线性筛法

原理

由于在埃氏筛法中，会多次去除同一个合数，这样会进行多次重复无意义的计算。

比如：

当前的数为 2 时，会去掉数 6

当当前的数变为 3 时，同样会去掉数 6

线性筛法的原理就是使去除同一个合数的操作只进行一次，即只使用当前合数的最小质因子将其去除。

代码

时间复杂度：\(O(n)\)

void get_primes(int n) {
    for (int i = 2 ; i <= n ; i ++ ) {
        if(!st[i]) primes[cnt ++ ] = i;
        for (int j = 0 ; primes[j] <= n / i ; j ++ ) {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
    return ;
}

这里有两个问题：

❤️ 为什么 primes[j] 即为 primes[j] * i 的最小质因子？

此时分为两种情况:

当 i % primes[j] == 0 时，因为 primes 是从小到大枚举，所以 primes[j] 一定是 i 的最小质因子，此时也一定是 primes[j] * i 的最小质因子。

当 i % primes[j] != 0 时，则 primes[j] 一定小于 i 的所有质因子，此时 primes[j] 一定为 primes[j] * i 的最小质因子。

❤️ 为什么当 i % primes[j] == 0 时 break 可以避免重复计算

当该情况成立时，则可设 i = primes[j] * d

若不退出循环，则 primes[j + 1] * i = primes[j + 1] * d * primes[j]

该式可以变化为 primes[j] * primes[j + 1] * d

那么 primes[j + 1] * d 在之前已经被 primes[j] 筛掉了

证毕