素数很有用，特别是在密码学领域中，比如RSA中很重要的一步就是寻找两个比较大的素数，通常的做法是先随机生成一个大整数，然后使用一些素性判定的方法，比如费马素性测试。在算法竞赛的数论题目中，素数也很常见，通常的做法是先找出一定范围内的所有素数，用到时再查表，筛法就可以做到。
1. 埃氏筛
埃拉托斯特尼筛法，简称埃氏筛。埃氏筛的原理是直观的，基于这样一个事实：素数不能被任意比它小的、除1以外的数整除；合数一定存在一个比它小且不为1的数整除。从2开始，当能确定一个数是质数时，就可以把这个数的整数倍标记为合数。从小到大遍历到一个数，如果它依然没有被标记为合数，那么就能确定它是质数。筛法中用到的数只有质数，筛选的对象是合数。这样做可以减少操作次数，并且可以筛掉所有的合数。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
bool isPrime[100000010];
//isPrime[i] == 1表示i是素数
int Prime[60000010], cnt;
//Prime存质数
int n, q, k;
void GetPrime(int n) {
memset(isPrime, true, sizeof(isPrime));
isPrime[1] = false;
isPrime[2] = true;
for(int i = 2; i <= n; i ++) {
if(isPrime[i]) {
Prime[cnt ++] = i;
for(int j = 2; i * j <= n; j ++) {
isPrime[i * j] = false;
}
}
}
}
2. 欧拉筛
埃氏筛存在重复筛的情况，欧拉筛可以保证范围内的每个合数都被筛掉，并且任一合数只被最小质因数筛掉，也就是只被筛一次。欧拉筛的时间复杂度为O(n)，因此也被成为线性筛。
先来看一下代码。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
bool isPrime[100000010];
//isPrime[i] == 1表示i是素数
int Prime[60000010], cnt;
//Prime存质数
int n, q, k;
void GetPrime(int n) {
memset(isPrime, true, sizeof(isPrime));
isPrime[1] = false;
isPrime[2] = true;
for(int i = 2; i <= n; i ++) {
if(isPrime[i]) {
Prime[cnt ++] = i;
}
for(int j = 0; j < cnt && i * Prime[j] <= n; j ++) {
isPrime[i * j] = false;
if(i % Prime[j] == 0) {
break; //保证只被“最小质因数 × 最大因数（非自己） = 这个合数”筛掉
}
}
}
}
线性筛的代码和埃氏筛很相似，比较明显的不同有两处，埃氏筛中的i一定是质数，而线性筛的i是小于等于n的所有数，Prime[j]一定是质数；另一个不同就是线性筛的条件判定提前结束内层循环。我们知道欧拉筛的线性时间复杂度是因为合数只被筛一次，也就是“最小质因数 × 最大因数（非自己） = 这个合数”，条件判定提前结束就保证了这件事。举一个例子，使用埃氏筛，30会被2(*15)、3(*10)和5(*6)筛三次，在线性筛中i依次遍历到2，3，5的时候是不可能筛掉30的，因为i只和小于自己的质数相乘，i遍历到6时，因为6能整除2，所以只会筛掉12，而不会筛掉和3、5相乘得到的18、30，这是因为对于30而言可以分解为6*5，而6可以整除2的话，那么必然可以将2分给5得到一个更大的数，也就是10，所以要结束。