Miller-Rabin素性判定算法是一种基于概率的判定算法，每次判定n是素数的正确性概率至少为75%，出错的概率小于25%。
如果对n进行k次素性检测，如果结果n为素数，那么n为合数的概率为1/(4^k)。如果k足够大，那么误判的概率就非常小。
算法原理如下：
#include <iostream>
#include <random>
#include <time.h>
using namespace std;
typedef unsigned __int64 llong;//无符号64位整形
//typedef为已有的类型起一个别名。
//既然是别名，对同一类型可以起多个别名。这在C/C++中是允许的，各个别名和真名的作用都是一样有效的。 llong mod_pro(llong x,llong y,llong n)
{
llong ret=0,tmp=x%n;
while(y)
{
if(y&0x1)
if((ret+=tmp)>n)
ret-=n;
if((tmp<<=1)>n)
tmp-=n;
y>>=1;//>>= 意思为：右移后赋值(按位移)
}
return ret; } //a^b mod c
llong mod(llong a,llong b,llong c)//a：原理中的b，b：m,c:n
{
llong ret=1;
while(b)
{
if(b&0x1)//b不为偶数
ret=mod_pro(ret,a,c);//1,随机数，n
a=mod_pro(a,a,c);
b>>=1;
}
return ret;
} llong ran()
{
llong ret =rand();
return ret*rand();
} bool is_prime(llong n,int t)//轮数为3
{
if(n<2)
return false;
if(n==2)
return true;
if(!(n&0x1))//按位与运算(为偶数)
return false;
llong k=0,m,a,i;
for(m=n-1; !(m&1); m>>=1,k++);// !(m&1):m是偶数
cout<<m<<" "<<k<<endl;//m是m，k是s：n-1= 2^s*m while(t--)
{
a=mod(ran()%(n-2)+2,m,n);//ran()%(n-2)+2：随机整数b
if(a!=1)//圈3
{
for(i=0; i<k&&a!=n-1; i++)
{
a=mod_pro(a,a,n);
}
if(i>=k)
return false;
}
}
return true;
} int main()
{ llong n;
cout<<"请输入一个大于三的整数：";
while(scanf("%I64u",&n)!=EOF)//__int64结构的输入格式
{
clockid_t starttime,endtime;
starttime=clock(); if(is_prime(n,3))
cout<<"YES\n";
else
cout<<"NO\n";
endtime=clock();
cout<<"用时"<<endtime-starttime<<"毫秒\n"<<endl;
cout<<"请输入一个大于三的整数：";
}
return 0;
}
学到了：
>>= 意思为：右移后赋值(按位移)
(n&0x1))//n和十六进制的1按位与运算(为偶数)
