检测n是否为素数，数据范围为2 <= n <= 10^18;
思路:Miller_Rabin素数检测模板题，原理:在Fetmat定理的基础之上，再利用二次探测定理；
对于任意的正整数p ，如果a^(p-1) % p != 1，则p一定不是素数，否则由Fermat定理，该数为素数的概率大于1/2;而MR检测中把p-1一直检测除以2直到为奇数为止，
由于当p为素数时x^2 % p = 1有x = 1或x = p-1;这样就把每次随机取值为素数的概率降到了1/4;同时Fermat里面还涉及到Carmichael数，这在MR检测中不存在；
ps:开始怀疑x*x会爆long long ,但是没有想到也将乘法变成加法。。太弱了；
#include<iostream>
#include<cstdio>
#include<time.h>
#include<stdlib.h>
using namespace std;
typedef long long ll;
int T,kase = ,i,j,k,n,m;
ll mult(ll x,ll y,ll mod) // 防止x*y爆long long;
{
ll ans = ;x %= mod;
while(y){
if(y&) ans += x, y--;
if(ans >= mod) ans -= mod;
y >>= ;
x <<= ;
if(x >= mod) x -= mod;
}
return ans;
}
ll pow(ll a,ll n,ll mod)
{
a %= mod;
ll ans = ;
while(n){
if(n&) ans = mult(ans,a,mod);
a = mult(a,a,mod);
n >>= ;
}
return ans;
}
bool Miller_Rabin(ll n)
{
if(n <= ) return n == ;
if(n% == ) return false;
ll t = n - ;
while(t% == ) t >>= ;
srand(time(NULL));
for(int i = ;i < ;i++){
ll p = rand()%(n-)+;
if(n%p == ) return false;
ll tmp = t;
ll x = pow(p,t,n); // p[i]^t % n;
while(tmp < n){
ll y = mult(x,x,n);
if(y == && x != && x != n-) return false;
x = y;
tmp <<= ;
}
if(x != ) return false; // Fermat检测
}
return true;
}
int main()
{
ll x;
scanf("%d",&T);
while(T--){
scanf("%lld",&x);
puts(Miller_Rabin(x)?"Yes":"No");
}
return ;
}