筛法求素数

埃拉特斯特尼筛法（埃氏筛）

原理：

当一个数是素数的时候，那么他的倍数肯定是合数。时间复杂度为 O(nloglogn)。

int isprime[MAXN];
int vis[MAXN];
void Prime(int n)
{
    int cnt = 0;
    memset(vis, 0, sizeof(vis));  //vis里0是素数，1是合数
    vis[0] = 1;
    vis[1] = 1;
    for (int i = 2; i < n; i++){
        if (!vis[i]){
            isprime[cnt++] = i;  //保存素数
            for (int j = i * i; j < n; j += i){
                vis[j] = 1;  //不是素数
            }
        }
    }
}

欧拉筛

原理：

首先，任何合数都能表示成一系列素数的积。然后利用了最小的素数因子，每个合数仅被它的最小素因子筛去正好一次。

时间复杂度为 O(n)。

int isprime[MAXN]; //保存素数
int vis[MAXN];    //初始化
void eulerSieve(int n)
{
    int cnt = 0;
    memset(vis, 0, sizeof(vis));  //0是素数，1是合数
    for (int i = 2; i < n; i++){
        if (!vis[i])
            isprime[cnt++] = i;
        for (int j = 0; j < cnt && i * isprime[j] < n; j++){
            vis[i * isprime[j]] = 1;
            if (i % isprime[j] == 0)
                break;
        }
    }
}

理解的难点就在于这一句

if (i % isprime[j] == 0) break;

这一句保证每个数只被它的最小质因子被筛一次，

对于一个数 a 假设它可以整除 isprime[ j ]，

即 a = isprime[ j ] * x，

那么 a * isprime[ j + 1 ] = isprime[ j ] * x * isprime[ j+1 ]，

所以 j 再往后就没有必要筛了，

因为 a * isprime[ j + 1 ] 肯定会在 i = x * isprime[ j + 1 ] 的时候被 isprime[ j ] 筛掉。