板子

int test[10]={0,2,3,5,7,11,13,17,19,23};
int qpow(int x,int p,int mod){
    int ans=1;
    while(p){
        if(p&1) ans=(ans*x)%mod;
        x=(x*x)%mod;
        p>>=1;
    }
    return ans;
}
int MillerRabin(int p){
    if(p==1) return 0;
    int k=0,t=p-1;
    while(!(t&1)) k++,t>>=1;
    for(int i=1;i<=8;i++){
        if(p==test[i]) return 1;
        int now=qpow(test[i],t,p),la=now;
        for(int j=1;j<=k;j++){
            now=(1ll*la*la)%p;
            if(now==1&&la!=1&&la!=p-1) return 0;
            la=now;
        }
        if(now!=1) return 0;
    }
    return 1;
}