Revise paste 93d9c112db0e1

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

long long binMultiply(long long a,long long b,long long n){
	long long res=0;
	while(b){
		if(b&1) res=(res+a)%n;
		a=(a+a)%n;
		b=b>>1;
	}
	return res;
}
long long binExp(long long a,long long b,long long n){
	long long res=1;
	while(b){
		if(b&1) res=binMultiply(res,a,n);
		a=binMultiply(a,a,n);
		b=b>>1;
	}
	return res;
}

bool check_composite(long long a,long long d,long long n,int s){
	long long x=binExp(a,d,n);
	if(x==1||x==n-1) return false;

for(int i=0;i<s-1;i++){
		x=binMultiply(x,x,n);

if(x==n-1) return false;
	}
	return true;
}
bool MillerRabin(long long n,int iter=5){
	if(n<4) return n==3||n==2;

int s=0;
	int d=n-1;
	while((d&1)==0){
		s++;
		d=d>>1;
	}

for(int i=0;i<iter;i++){
		int a=2+rand()%(n-3);
		if(check_composite(a,d,n,s)) return false;
	}

return true;

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
	int t;cin>>t;
	while(t--){
		long long n;cin>>n;
	    if(MillerRabin(n)) cout<<"YES"<<endl;
	    else cout<<"NO"<<endl;
	}

return 0;
}