素数筛

什么是素数筛？

素数筛是一种求所有小于n的所有素数的方法，把从2开始的所有合数逐步筛掉留下素数。

埃氏筛

埃氏筛的思路非常简单，从2开始筛去2的所有倍数，接着从剩下的最小数字3开始，筛去3的所有倍数，依次下去，每一次都筛去上一次剩下的数中最小的数k的所有倍数，最后剩下的数就是2～n中所有的素数。

那为什么剩下的数中最小的就一定是素数呢？因为一个数的因子一定是不超过其本身的，而小于这个数的所有倍数均已经被筛去了，所以剩下的数中最小的就一定是素数。

埃氏筛实现

bool vis[MAXN]; //用于标记下标i是否是素数
int prime[MAXN], x; //prime用于存放素数，x是prime数组的下标指针
void PrimeFilter(int n){ //埃氏筛 时间复杂度：O(nloglogn)
    vis[0] = vis[1] = true;
    for(int i = 2; i <= n; i++){
        if(!vis[i])prime[x++] = i;
        for(int j = 2; j * i <= n; j++)vis[i*j] = true; //将这个素数的所有倍数筛掉
    }
}

欧拉筛

在埃氏筛的步骤中我们可以发现，一个合数可能被多次筛去，比如6，即是2的倍数，也是3的倍数，被筛去了两次，这样浪费了很多时间。欧拉筛的基本思想就是让每个合数只被它的最小质因数筛去一次，避免重复。

欧拉筛实现

void EulaFilter(int n){ //欧拉筛
    vis[0] = vis[1] = true;
    for(int i = 2; i<=n; i++){
        if(!vis[i])prime[x++] = i;
        for(int j = 0; j < x; j++){
            if(i * prime[j] > n)break;
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0)break;
        }
    }
}