3. 筛质数
1.朴素做法 ----O(n∗logn)O(n∗logn)
原理: 2 - p - 1中的数都没有把 p 删掉,说明 p 不是 2 - p - 1 当中任何一个数的倍数,因此 p 是一个质数.

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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){//依次删掉每个i的倍数
            st[j] = true;
        }
    }
}
2.改进版 ---- O(n∗loglogn)O(n∗loglogn) (埃氏筛法)

质数定理：1 - n 当中, 有 n / lnn 个质数.

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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){//只删掉质数i的倍数
                st[j] = true;
            }
        }
    }
}
2.终极版 ---- O(n)O(n) (线性筛法)

核心：每个 n 只会被它的最小质因子筛掉.

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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;//primes[j]一定是i的最小质因子
        }
    }
}
分析：
1.i % primes[j] == 0, 说明：primes[j]一定是i的最小质因子,primes[j]一定是primes[j] * i的最小质因子
2.i % primes[j] != 0, 说明: primes[j]一定小于i的所有质因子,primes[j]一定是primes[j] * i的最小质因子
综上：primes[j]一定是primes[j] * i的最小质因子.

我们用最小质因子筛,而每个数只有一个最小质因子,因此每个数只会被筛一次,所以是线性的.

注意：如果在1e6左右,埃氏筛法和线性筛法差不多,但在1e7左右,线性筛法要比埃氏筛法快几倍.在实际应用中线性筛法用的比较多,埃氏筛法用的较少,但埃氏筛法的思想很重要.