（本文大量参考算法竞赛进阶指南）
0、定义
质数定义为：若一个大于 $1$ 的正整数，无法被除了 $1$ 和它自身以外的其他任何正整数整除，即称该数为质数。
相应的，剩下的正整数，除了 $1$ 之外，称为合数。
应当注意的一点：质数的数量不多，分布稀疏，对于一个足够大的正整数 $N$，不超过 $N$ 的质数大约有 $frac{N}{ln N}$ 个，即每 $ln N$ 个正整数中，大约有一个质数。
1、素数判定
1.1、试除法
对于要判定的正整数 $N$，用 $2 sim lfloor sqrt{N} floor$ 进行试除，这是很朴素自然的一种做法，时间复杂度 $O(sqrt(N))$。
1.2、费马素性检验
费马小定理：如果 $p$ 是一个质数，且正整数 $a$ 与 $p$ 互质，则有 $a^{p-1} ≡ 1 pmod p$。
这个定理的逆命题，在一定程度上可以用来检测素数，存在反例：
虽然 $2^{340} mod 341 = 1$，但 $341=11 imes 31$。后来，人们又发现了 $561, 645, 1105$ 等数都表明 $a=2$ 时费马小定理的逆命题不成立。因此，引出伪素数的概念：若 $n$ 能整除 $2^{n-1}-1$（换句话说，$2^{n-1}-1$ 能被 $n$ 整除），但同时 $n$ 又是合数，那么 $n$ 就是伪素数。因此，伪素数不一定是素数，不满足 $2^{p-1} mod p = 1$ 的一定是合数。
当然，$a=3,4,5,cdots$ 时，又会有不一样的情况，因此称：满足 $a^{n-1} mod n = 1$的合数 $n$ 叫做以 $a$ 为底的伪素数。
因此，随机选择若干个小于待测数的正整数作为底数 $a$ 进行若干次测试，只要有一次没有通过测试就立刻可判定为合数。这就是费马素性检验。
再有关于卡迈克尔数的定义：对于合数 $n$，如果对于所有满足与 $n$ 互质的正整数 $a$，都有同余式 $a^{n-1} ≡ 1 pmod n $ 成立，则合数 $n$ 为卡迈克尔数。尽管卡迈克尔数很少（在 $1 sim 1e8$ 范围内的整数中，只有 $255$ 个卡迈克尔数），但依然使得我们无法使用费马素性检验。
1.3、Miller-Rabin素性检验
定理：如果 $p$ 是素数，$x$ 是小于 $p$ 的正整数，且 $x^2 ≡ 1 pmod p$，那么要么 $x=1$，要么 $x=p-1$。
证明：因为 $x^2 ≡ 1 pmod p$ 相当于 $x^2 - 1$ 能被 $p$ 整除，也即 $p$ 能整除 $(x+1)(x-1)$。由于 $p$ 是素数，那么只可能是 $x-1$ 能被 $p$ 整除，此时 $x=1$，或 $x+1$ 能被 $p$ 整除，此时 $x=p-1$。
因此，将上述定理应用于伪素数 $341$ 的费马素性检验：
由于 $2^{340} mod 341 = 1$，即 $(2^{170})^2 ≡ 1 pmod{341}$，假定 $341$ 是素数，那么应当有 $2^{170} ≡ pm 1 pmod{341}$，算得 $2^{170} mod 341$ 确实等于 $1$ 时，我们可以继续查看 $2^{85} mod 341$ 的结果。我们发现，$2^{85} mod 341=32$，因此 $341$ 不是素数。
Miller-Rabin素性检验同样有较小的概率把合数错判为质数，我们把可以通过以 $a$ 为底的Miller-Rabin素性检验的合数称作以 $a$ 为底的强伪素数。
给出一个Miller-Rabin素性检验模板：
namespace MR { int test[4]={2,3,5,7}; ll Pow(ll a,ll n,ll mod) { ll res=1, base=a%mod; while(n) { if(n&1) res*=base, res%=mod; base*=base, base%=mod; n>>=1; } return res%mod; } bool Test(int p) { if(p<=1) return 0; int t=p-1, cnt=0; while(t%2==0) t>>=1, cnt++; for(int i=0;i<4;i++) { if(p==test[i]) return 1; ll now=Pow(test[i],t,p), nxt; for(int j=1;j<=cnt;j++) { nxt=(now*now)%p; if(nxt==1 && now!=1 && now!=p-1) return 0; now=nxt; } if(now!=1) return 0; } return 1; } }
在HIT1356上进行了验证，在洛谷3383上进行了验证，手动验证在$[0,1e8]$ 范围内全部正确。
2、素数筛
2.1、埃筛
埃筛基于这样一个很简单的想法：对于任意质数 $x$，其倍数 $2x,3x,cdots$ 均不是质数。筛不超过 $N$ 的素数，埃筛时间复杂度是 $O(N log log N)$。
代码：
const int MAX=2e7; int tot,prm[MAX/15]; bool noprm[MAX+3]; void Erato() { tot=0; noprm[0]=noprm[1]=1; for(int i=2;i<=MAX;i++) { if(noprm[i]) continue; prm[tot++]=i; for(int j=i;j<=MAX/i;j++) noprm[i*j]=1; } }
（注：开数组时注意不超过 $N$ 的质数大约有 $frac{N}{ln N}$ 个）
在http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=2验证了上述代码。
2.2、欧拉筛
欧拉筛是线性筛，筛不超过 $N$ 的素数其时间复杂度是 $O(N)$。
不难发现埃筛会对一些合数重复标记，因此考虑优化，对于任意一个合数，只用其最小质因子将其筛去。
假设数组 $v$ 是记录每个数的最小质因子的，因此欧拉筛可以描述为：
①依次考虑 $2 sim N$ 的每个数 $i$；
②若 $v[i]=i$，即最小质因子是其本身，那么 $i$ 即为质数。
③遍历不超过 $v[i]$ 的每个素数 $p$，令 $v[i*p]=p$，即整数 $i*p$ 的最小质因子为 $p$。
代码大概可以描述成：
void Euler() { tot=0; for(int i=2;i<=MAX;i++) { if(v[i]==0) v[i]=prm[tot++]=i; for(int j=0;j<tot;j++) { if(prm[j]>v[i] || prm[j]>MAX/i) break; v[i*prm[j]]=prm[j]; } } }
然后，我们发现并不一定需要维护最小质因子，也可以优化成如下代码：
const int MAX=2e7; int tot,prm[MAX/15]; bool noprm[MAX+3]; void Erato() { tot=0; noprm[0]=noprm[1]=1; for(int i=2;i<=MAX;i++) { if(!noprm[i]) prm[tot++]=i; for(int j=0;j<tot && prm[j]<=MAX/i;j++) { noprm[i*prm[j]]=1; if(i%prm[j]==0) break; } } }
在http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=2验证了上述代码。
2.3、两种筛法的比较
其实埃筛 $O(N log log N)$ 的时间复杂度很接近线性，我们可以对埃筛和欧拉筛进行耗时的比较：
令 $N=5e6$，分别运行50次埃筛和欧拉筛，耗时比较：
令 $N=6e6$，分别运行50次埃筛和欧拉筛，耗时比较：
大概可以认为，大约在 $N le 5e6$ 时，埃筛更优，大约在 $N > 5e6$ 时，欧拉筛更优。