MR素数测试

用来快速判断一个数是否为素数
期望时间复杂度O(logn),单次最坏时间复杂度O(lognxlogn)

ll ksc(int a,int b,int p){ll z = (long double)a/p*b;ll res =(ull)a*b -(ull)(z*p);return (res+p)%p;
}
int ksm(int a,int b,int p){int res=1;while(b){if(b&1)res=ksc(res,a,p);a=ksc(a,a,p);b>>=1;}return res%p;
}
int mr(int a,int p){if(ksm(a,p-1,p)!=1)return 0;int x= p-1,y=0;while(x%2==0){x>>=1;y=ksm(a,x,p);if(y!=1&&y!=p-1)return 0;if(y==p-1)return 1;}return 1;
}
int isprime(int x){if(x<2)return 0;if(x==2||x==3||x==5||x==7||x==43)return 1;return mr(2,x)&&mr(3,x)&&mr(5,x)&&mr(7,x)&&mr(43,x);
}