在素数筛法当中，首先先讲一下朴素的筛法和埃氏筛。
朴素筛法：对于任何一个数i，我们从2到sqrt(i)挨个枚举看是不是i都无法整除这些数，如果是的话那么就说明i是素数，反之则不是
埃氏筛：我们发现，在朴素筛法当中我们希望枚举每个数的因子，也就是说，当我们判断4是不是素数，我们枚举了2，判断6是不是素数，又枚举了2，那我们可不可以在判断2是不是素数的时候，发现2是素数，就直接把它的倍数都筛掉。这就是埃氏筛。
#include<bits/stdc++.h>
using namespace std;
int n,tot;
int Prime[100010];
bool vis[1000010];
int main() {
cin >> n;
for(int i = 2;i <= n;i++) {
if(!vis[i]) {
Prime[++tot] = i;
for(int j = 2;j * i <= n;j++)
vis[j * i] = true;
}
}
for(int i = 1;i <= tot;i++)
cout << Prime[i] << " ";
return 0;
}
欧拉筛：尽管埃氏筛貌似已经非常优秀了，但是我们仍然发现它也并不是那么令人满意，因为，以18这个数为例，我们在判断2为素数的时候，就用2把18筛掉了，然而当我们在判断3为素数的时候，又把18筛掉了一遍，这样就造成了冗余的操作从而浪费了时间。那么怎么保证一个数一定只被筛掉一遍呢？这就是欧拉筛的核心思想，一个数如果不是素数，那么一定只被它的最小的素数因子筛掉。同样地以18为例，2×9=18，3×6=18，那么我们就在2的时候用2×9来筛掉18。那么问题是，怎么样保证只用2来筛掉18.这里给出一个感性证明，当我们枚举到6的时候，第二层循环枚举素数枚举到2，用6×2筛掉12后，此时我们就应该break掉不再枚举6乘2以后的素数，因为当前这个数（即6）一定可以拆成当前素数2乘上另外一个数，那么2以后的素数，也就是3，5等，我们发现6×3可以拆成2×3×3，也就是2×9，6×5可以拆成2×3×5，也就是2×15，那么我么完全可以在枚举到数9和15的时候再把18、30筛掉而不必现在就筛。而2一定比后面的这些素数小（因为它先被枚举到），那么就可以放心的break掉了，这就保证了一个数一定只被它最小的质因子筛掉而又不会漏筛。
#include<bits/stdc++.h>
using namespace std;
int n,tot;
int Prime[100010];
bool vis[1000010];
int main() {
cin >> n;
for(int i = 2;i <= n;i++) {
if(!vis[i]) Prime[++tot] = i;
for(int j = 1;j <= tot && i * Prime[j] <= n;j++) {
vis[i * Prime[j]] = true;
if(i % Prime[j] == 0) break;
}
}
for(int i = 1;i <= tot;i++)
cout << Prime[i] << " ";
return 0;
}