数论模板

ll a[5]= {2,3,5,7,11};
ll quickpower(ll a,ll n,ll p)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=(a*ans)%p;
        n=n>>1;
        a=(a*a)%p;
    }
    return ans;
}
bool judge(ll a,ll x,ll t,ll n)
{
    ll ret=quickpower(a,x,n);
    if(ret==n-1||ret==1) return false;
    for(int i=0; i<t; i++)
    {
        ret=ret*ret%n;
        if(ret==n-1) return false;
    }
    return true;
}
bool miller_rabbin(ll n)
{
    if(n==2||n==3||n==5||n==7||n==11) return true;
    if((n&1)==0||n%3==0||n%5==0||n%7==0||n%11==0) return false;
    if(n<2) return false;
    ll t=0,x=n-1;
    while(!(x&1))
    {
        t++;
        x=x>>1;
    }
    ll i;
    for(i=0; i<5; i++)
    {
        if(judge(a[i],t,n)) return false;
    }
    return true;
}