Miller-Rabin

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;