Miller-Rabin 求调

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int now=0,nev=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')nev=-1;c=getchar();}
	while(c>='0'&&c<='9'){now=(now<<1)+(now<<3)+(c&15);c=getchar(); }
	return now*nev;
}

int qpow(int a, int b, int p){
	int ans = 1;
	for (; b; b >>= 1){
		if (b & 1) ans = ans * a % p;
		a = a * a % p;
	}
	return ans;
}

bool witness(int a, int n){
	int u = n - 1;
	int t = 0;
	while (u & 1 == 0)
		u >>= 1, t ++;
	int x1, x2;
	x1 = qpow(a, u, n);
	for (int i = 1; i <= t; i ++){
		x2 = qpow(x1, 2, n);
		if (x2 == 1 && x1 != 1 && x1 != n - 1)
			return true;
		x1 = x2;
	}
	if (x1 != 1) return true;
	return false;
}

int miller_rabin(int n, int s){
	if (n < 2) return 0;
	if (n == 2) return 1;
	if (n % 2 == 0) return 0;
	for (int i = 0; i < s && i < n; i ++){
		int a = rand() % (n - 1) + 1;
		if (witness(a, n)) return 0;
	}
	return 1;
}

signed main()
{
	srand(time(0));
 	int m = read();
 	while (m --){
 		int n = read();
 		int S = 50;
 		if (miller_rabin(n, S)) cout << "YES\n";
 		else cout << "NO\n";
	}
    return 0;
}