```cpp
#include <iostream>
#define int long long
using namespace std;
int qmul(int x,int y,int p){
if(y==0) return 0%p;
int res=0;
while(y){
if(y&1) res=(res+x)%p;
x=(x+x)%p;
y>>=1;
}
return res;
}
int qpow(int x,int y,int p){
if(y==0) return 1%p;
int res=1;
while(y){
if(y&1) res=(res*x)%p;
x=(x*x)%p;
y>>=1;
}
return res;
}
int tpr[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
bool Miller_Rabin(int x){
if(x==2) return true;
if(x<2||(!(x&1))) return false;
int y=x-1,t=0;
while(!(y&1)) y>>=1,t++;
for(int ii=0;ii<25;ii++){
int tmp=tpr[ii];
if(x==tmp) return true;
if(x%tmp==0) return false;
int a=qpow(tmp,y,x);
for(int i=1;i<=t;i++){
int b=qmul(a,a,x);
if(b==1&&a!=1&&a!=x-1) return false;
a=b;
}
if(a!=1) return false;
}
return true;
}
int t,n;
signed main(){
cin>>t;
while(t--){
cin>>n;
if(Miller_Rabin(n)) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
```
by charleshe @ 2023-01-21 17:26:49
@[charleshe](/user/477258) 因为可能会爆```long long ``` ,所以要用 ```_int128```,不然就要边乘边模。
by _zexal_ @ 2023-07-09 20:26:31