质数定义
不能被 \(2，3，...，n-1\) 整除的自然数 \(n\) 称之为素数，或质数。
判断单个质数 isPrime
那是不是一定要判断从 2 到 n-1 每个数能否整除 n 呢？
答案是不需要。
如果 k 整除 n，那么 n/k 也整除 n，它两位于 \(\sqrt n\) 两侧，判断了 k ，也就判断了 n/k，不需要重复判断，我们只需要从 2 遍历到 \(\lfloor \sqrt n \rfloor\)（向下取整）。isPrime 函数代码如下：
bool isPrime(int n){
if(n <= 1) return false;
int sqrtn = (int)sqrt(1.0 * n); //n 乘以 1.0 变成浮点型
for(int i = 2; i <= sqrtn; i++){
if(n % i == 0) return false;
}
return true;
}
或者这样写，
bool isPrime(int n){
if(n <= 1) return false;
for(int i = 2; i * i <= n; i++){
if(n % i == 0) return false;
}
return true;
}
这样写就得注意 n 的大小是否超过了 int 的范围。
素数筛
前面是对单个数的判断，其时间复杂度为 \(O(\sqrt n)\)，如果要判断 n 个数，就会达到 \(\mathbf{O(n\sqrt n)}\)。
素数筛的出现就是为了在较短时间复杂度内“筛出”一段范围内的所有质数。
埃氏筛
埃拉托斯特尼筛法（Sieve of Eratosthenes）。
const int maxn = 101;
int primes[maxn], pNum = 0;// primes 存储范围内的素数，pNum 是素数个数
bool notPrime[maxn] = { 0 };// 筛，标记素数，素数标记为 false
void Find_Prime(){
for(int i = 2; i < maxn; i++){
if(!notPrime[i]){// i 为素数
primes[pNum++] = i; //存储素数
for(int j = 2 * i; j < maxn; j += i){
notPrime[j] = true; // 筛，筛掉 i 的所有倍数
}
}
}
}
筛掉 i 的倍数就会筛掉部分非素数，那下一个数一定是素数吗？一定是，因为遇到下一个素数 x 时，x 前面的所有数要么是素数，要么被素数筛掉了，既然 x 没有被筛掉，说明它前面没有整除它的数。
时间复杂度：\(\mathbf{O(\sum_{i=1}^{n}{(\frac{n}{i})})=O(n\log \log n)}\)
改进：
for(int j = i * i; j < maxn; j += i){
notPrime[j] = true; // 筛，筛掉 i 的所有倍数
}
不用从 2 * i 开始筛除，因为已经被 i 前面筛除过了。
欧式筛
欧式筛时间复杂度为 \(O(n)\)