菜到掉渣

#include<iostream>
#include<algorithm>
#include<map>
#include<ctime>
using namespace std;
typedef long long ll;
ll mul(ll a,ll b,ll p){
    ll res=0;
    for(;b;b>>=1){
        if(b&1) res=(res+a)%p;
        a=(a+a)%p;
    }
    return res;
}
ll pow(ll a,ll b,ll p){
    ll res=1%p;
    for(;b;b>>=1){
        if(b&1) res=(res*a)%p;
        a=(a*a)%p;
    }
    return res;
}

bool miller_rabin(ll n,ll times){
    if(n==2||n==3) return true;
    if(n%2==0||n==1) return false;
    ll d=n-1,s=0;
    while(!(d&1)) d>>=1,s++;
    srand((unsigned)time(NULL)); 
    while(times--){
        ll a=rand()%(n-3)+2;
        ll x=pow(a,d,n),y=0;
        for(int j=0;j<s;j++){
            y=mul(x,x,n);
            if(y==1&&x!=1&&x!=(n-1)) return false;
            x=y;
        }
        if(y!=1) return false;
    }
    return true;
}
int main(){
    ll n,x;
    cin>>n;
    while(n--){
        cin>>x;
        if(miller_rabin(x,50)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}