费马小定理：对于任意一个质数满足：\(a^{p-1}\equiv1\pmod p\)
二次探测：对于任意一个奇质数满足：\(x^2\equiv1\pmod p\) 的解为 \(x=1\) 或 \(x=p-1\)
将两个定理结合起来，设 \(p-1=u\times 2^t\)，那么计算出 \(a^u\) 次方后不断进行平方计算，如果某次平方后得到了 1 并且平方的数不为 \(1\) 或 \(p-1\)，那么 \(p\) 肯定不是质数。
据说 \(a\) 选取前 13 个质数就行了，也可以使用下面程序给的数字列表。注意特判偶数和小于 3 的情况
int prime(LL n)
{
if(n<3||n%2==0)
return n==2;
LL t=n-1;
int s=0;
while(!(t&1))
t>>=1,s++;
static const int pr[]={2,325,9375,28178,450775,9780504,1795265022};
for(int i=0;i<7;i++)
{
int x=pr[i];
LL v=pown(x,t,n);
if(v==1||!v||v+1==n)
continue;
for(int j=1;j<=s;j++)
{
v=(LLL)v*v%n;
if(j^s&&v==n-1)
{
v=1;
break;
}
if(v==1)
return 0;
}
if(v^1)
return 0;
}
return 1;
}
···