什么是素数筛？
素数筛是一种求所有小于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;
}
}
}
