有一个正整数 (n) ，试判断 (n) 是不是质数。
经典模板了属于是
主要有质数筛、枚举因子、Miller Rabin 算法三种做法
1. 质数筛
分为埃氏筛和欧拉筛（线性筛）两种
埃氏筛应该是判断质数的最基础方法了
从 (2) 开始从小到大依次枚举整数
如果没被筛过就说明是质数，同时应将其所有倍数（除本身外）筛去
v[1]=1; // 值为 1 表示非质数，0 表示是质数
for (int i=2; i<=n; ++i) if (!v[i])
for (int j=(i<<1); j<=n; j+=i) v[j]=1;
时间复杂度 (O(nlog log n))
欧拉筛同样是筛倍数，但用了一些技巧将时间复杂度降至了 (O(n))
v[1]=1;
for (int i=2; i<=n; ++i) {
if (!v[i]) p[++cnt]=i;
for (int j=1; j<=cnt&&p[j]*i<=n; ++j) {
v[p[j]*i]=1;
if (i%p[j]==0) break;
}
}
关键在于每个数恰好被其最小质因子筛一次
看懂这个结论之后 正确性和时间复杂度就都很显然了
2. 枚举因子
质数的定义：只有两个正因数（(1) 和本身）的自然数是质数。
所以只需判断 (2sim n-1) 中有没有 (n) 的因子
(x) 的因子是成对出现的，每一对因子中较小者必然不超过 (sqrt n) ，因此从 (2) 枚举到 (sqrt n) 即可
int isp(int x) { //判断质数，是则返回 1 ，否则返回 0
if (x==1) return 0; // 1 既不是质数也不是合数
for (int i=2; i*i<=x; ++i)
if (x%i==0) return 0;
return 1;
}
时间复杂度为 (O(sqrt n))
细想一下发现仅枚举质因子即可保证正确性
所以有一种优化思路是尽量避免枚举合数
考虑如下结论：
大于 (3) 的质数必然和 (6) 的倍数相邻。
设 (k) 为正整数，则 (6k-2,6k,6k+2,6k+3) 显然都为合数
因此只需枚举形如 (6kpm 1(kinmathbb N^*)) 的数即可
int isp(int x) {
if (x<5) return (x==2||x==3); // 注意 2,3 需要特判
if (x%6!=1&&x%6!=5) return 0;
for (int i=5; i*i<=x; i+=6)
if (x%i==0||x%(i+2)==0) return 0;
return 1;
}
时间复杂度依然为 (O(sqrt n)) ，但实际运行要比优化前快几倍，而且代码也不长，日常做题推荐使用
3. Miller-Rabin 素性检测
这篇文章讲得非常详细了：link
时间复杂度 (O(klog n)) ，其中 (k) 为测试次数
OI 中可以选择固定的几个常数做测试，在保证准确的前提下：
(2^{32}) 以内选择 (2,7,61) 三个数即可
(10^{16}) 以内选择 (2,3,7,13,61,24251) 六个数即可
数据范围更大时还是建议换成随机数，具体实现可参考上面提到的文章
4. 总结
| 算法 | 时间复杂度 |
空间复杂度 |
|---|---|---|
| 线性筛 | (O(n)-O(1)) | (O(n)) |
| 埃氏筛 | (O(nlog log n)-O(1)) | (O(n)) |
| 暴力 | (O(sqrt n)) | (O(1)) |
| Miller-Rabin | (O(klog n)) | (O(k)) |
(O(n)-O(1)) 表示预处理 (O(n)) ，回答单次询问 (O(1)) （埃氏筛时间复杂度同理）
如果数据范围较小，用暴力随便搞搞就行了
如果询问次数很多且 (n) 不是很大，应使用筛法（推荐线性筛）
Miller-Rabin 代码量大，写起来比较耗时，尽量少用
考场上很少会出现必须用 Miller-Rabin 的情况，所以这个算法不用练得太熟 差不多得了