http://miller-rabin.appspot.com/
struct MillerRabin
{
const int base[14]=
{0,2,3,5,7,11,13,17,19,23,29,31,37,41};
static ll qmul(ll x,ll y,ll mod)
{
if(x>=mod)x%=mod;
if(y>=mod)y%=mod;
ll res=0;
for(;y;y>>=1)
{
if((y&1) && (res+=x)>=mod)
res-=mod;
if((x+=x)>=mod)x-=mod;
}
return res;
}
static ll qpow(ll x,ll y,ll mod)
{
if(x>=mod)x%=mod;
ll res=1;
for(;y;y>>=1,x=qmul(x,x,mod))
if(y&1)res=qmul(res,x,mod);
return res;
}
bool test(ll n)
{
if(n==2)return true;
if(n<=1 || !(n&1))return false;
ll u;for(u=n-1;!(u&1);u>>=1);
for(int i=1;i<=13 && base[i]<n;++i)
{
ll x=qpow(base[i],u,n),y;
for(ll v=u;v<=n;x=y,v<<=1)
{
y=qmul(x,x,n);
if(y==1 && x!=1 && x!=n-1)
return false;
}
if(x!=1)return false;
}
return true;
}
}MR;
