快速线性筛选法

#include<bits/stdc++.h>
#define ll long long
#define fo(i, j, n) for(int i=j; i<=n; ++i)
using namespace std;
const int MAXN = 2e7;

int prime[MAXN+1];
int minPrime[MAXN+1];
void getPrime(){
    memset(prime, 0, sizeof(prime));
    fo(i, 2, MAXN){
        if(!prime[i]){
            prime[++prime[0]] = i;
//          minPrime[i] = i;
        }
        for(int j=1; j<=prime[0] && prime[j]*i<=MAXN; ++j){
            prime[prime[j]*i] = 1;
//          minPrime[prime[j]*i] = prime[j]; // 最小素数
            if(i % prime[j] == 0) break;
        }
    //  printf("%d %d\n", i, minPrime[i]);
    }
//  printf("ok");
} 

现在具体讲解一下证明：
最难理解的是：
要从下面两个方面：
每个数至少被访问一次
每个数至多被访问一次
进行理解.
对于质数，一定会在i的循环中访问到，并确定为质数。
对于合数，一定可以分解为一个最小素因子和其他数的乘积。
比如：
合数 i = p（最小素因子）* a;
若 i%prime[k] ==0;
则 p * a * prime[k+1] 可以被后面的 a * prime[k+1] 再乘以素数 p 筛选出来，
你可能会问,不会被prime[k]*a 乘 p 筛选出来吗？
不会的，这里的p 其实就是prime[k]，所以prime[k]*a就是i,而i就是本轮晒选…只能由更大的i来筛选，但是那至少也是下一轮之后的事情了
为了不出现重复筛选所以就有了整除便break
显然prime[k]小于prime[k+1],所以i%prime[k] == 0 时要停止。