费马素性检验
根据费马小定理，如果p是素数，则$a^{p-1}≡1(\ mod\ p)$ 对所有的 $a∈[1,n-1] $ 成立
。所以如果在 [1,n-1] 中随机取出一个 a，若发现不满足费马小定理，则证明n必为合数。
注意！！！如果整数 a 不是 p 的倍数，且 $ a^{p-1}\equiv 1\pmod p $，那么 p 也不一定是一个素数
一个反例就是著名的 Carmichael 数。这一类数可以通过所有的费马素性检验，但它们是合数。所以费马素性检验是概率性的。但 Carmichael 数是很稀少的（最小的是561），所以该种方法可以在大部分情况下做出正确的判断。
选择一些比较小的数作为 a ，并依次带入费马小定理中。注意要多选一些，以使得正确率更大。只要有一个不通过就判定为合数。如果全部通过，则将该数判定为素数。
bool primecheck(int p)
{
for(int i=2;i<=10;i++)
if(pow(i,p-1)%p!=1)//费马小定理
return false;
return true;
}Miller-rabin算法
二次探测
- 1.对于质数 p 满足 $φ(p)=p-1$ ↩
