素数是一类很奇妙的数字，不仅本身具有“只有1和本身两个因数”的性质，而且在很多著名的函数和算法中都有它的参与。所以从给定的一堆数中快速筛选出素数是一个很常见的需求——各种各样的素数筛法应运而生。
朴素筛法
法如其名，就是一种利用素数基本性质的筛法：对于每一个数，枚举1到$\sqrt n$ 的数判断是可以被n整除——其实就是对每一个数进行了一次素数判断，显然不怎么高效。
Eratosthenes 筛法（埃氏筛）
Eratosthenes 筛法即埃氏筛，运用了“以小标大”的思想：对于一个素数 x，它的倍数 ax 一定是一个合数。所以对于一个素数，我们就需要把它在给定范围内的倍数全标记为合数——当枚举到一个已经被标记为合数的数时就可以直接跳过，避免冗余的判断，运行一次 Eratosthenes 筛法，没有被标记的数就是素数了。
另外，我们可以发现 2 和 3 都会将 6 标记为合数——事实上任何小于 x^2^ 的 x 的倍数，都会被比 x 更小的素数标记，所以为了减少重复标记，可以从 x^2^ 开始标记。
bool isPrime[maxn];
int primeNumber[maxn],primeCount;
void primeEratosthenes(int n){
primeCount=0;
for(int i=1;i<=n;i++) isPrime[i]=true;//As 2 is a prime number
isPrime[0]=isPrime[1]=false;
for(int i=2;i<=n;i++){
if(isPrime[i]){
primeCount++;
primeNumber[primeCount]=i;//If current number is a prime then put into the prime colletion
for(int j=i*i;j<=n;j*=i) isPrime[j]=false;//And mark its multiple as "non-prime" (starts from i*i)
}
}
return;
}
Eratosthenes 筛法的时间复杂度为 $O(nloglogn)$，效率很高接近线性，但是即使是在优化后还是会有重复标记——一个简单的例子：12 既被 2 标记又被 3 标记。
线性筛法（欧拉筛）
上面的 Eratosthenes 筛法固然很优秀——事实上它因为代码少，思想简单，而且时间复杂度足够优秀，成为 OI 中最常用的素数筛法——但是仍存在重复标记的情况。还有一种更加高效的筛法——线性筛法。
先来总结一下 Eratosthenes 筛法出现重复的经验：它通过单纯标记倍数的方法标记合数，但是 12 既是 2 的倍数 又是 3 的倍数，虽然通过从 x^2^ 开始标记的方法避免了 6 被重复标记，但是其他 2 和 3 的公倍数，即所有 6 的倍数都会被 2 和 3 标记。
出现重复标记，究其原因是没有对每一个合数进行不重不漏的分类来确定它应该被哪个素数标记：在上面的例子中，12 被分解为 2 x 6，也被分解为 3 x 4。线性筛法使用最小素因子来去确定一个合数应该被哪个素数标记——对于 12，在线性筛法中被分解为 2 x 2 x 3，最小素因子是 2，那么就没 3 啥事了。使用一个数组minimizedPrimeFactor[] 来记录一个数的最小素因子：
- 若有
minimizedPrimeFactor[x]==x则 x 是一个素数，把它保存下来。 - 扫描每一个不大于
minimizedPrimeFactor[x]的素数 y，并令minimizedPrimeFactor[x*y]=y——由于 x 中没有比minimizedPrimeFactor[x]更小的素因子，且 y 是更小的素数，所以 x*y 的最小素因子一定是 y。
其线性的时间复杂度很容易证明：每一个合数只会被它的最小素因子筛一次，所以时间复杂度显然为$O(n)$。
int minimizedPrimeFactor[MaxN],primeNumber[MaxN],primeCount;
void Eular(int n){
memset(minimizedPrimeFactor,0,sizeof(minimizedPrimeFactor));
primeCount = 0;
for(int i = 2; i <= n; i++){
if(minimizedPrimeFactor[i] == 0){
minimizedPrimeFactor[i] = i;//The minimized prime factor of a prime number is itself
primeNumber[++primeCount] = i;
}
for(int j = 1; j <= primeCount; j++){
if(primeNumber[j] > minimizedPrimeFactor[i] || primeNumber[j] > n/i) break;//j should be a prime, and be smaller than the minimized prime factor of i; i*j should be in the range
minimizedPrimeFactor[i * primeNumber[j]] = primeNumber[j];
}
}
return;
}