费马小定理
\(p\) 为素数且 \(a\bot p\)，有 \(a^{p-1}\equiv 1(\mod p)\)
二次探测定理
\(p\) 为素数且 \(a^2\equiv1(\mod p)\)，那么 \(a\equiv\pm1(\mod p)\)
素数
\(p\) 为素数，那么 \(p=2\) 或者 \(2\nmid p\)
把这三个结合起来，先判断 \(2\) 的倍数
虽然逆定理不一定对，但是结合一下大概率对
费小马定理 \(p-1\) 肯定能写成平方的形式
结合二次探测定理，随机数判断是不是素数
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, n, mx=7;
int pi[10]={2,3,5,7,11,13,17};
int mul(int a,int b,int p) {
int res=0;
for( ; b; b>>=1) {
if(b&1) res=(res+a)%p;
a=a*2%p;
}
return res;
}
int fpow(int a,int b,int p) {
int res=1;
for( ; b; b>>=1) {
if(b&1) res=mul(res,a,p);
a=mul(a,a,p);
}
return res;
}
int mr(int x,int a) {
int d=x-1, r=0;
while(!(d&1)) d>>=1, r++;
int qwq=fpow(a,d,x);
if(qwq==1) return 1;
while(r--) {
if(qwq==x-1) return 1;
qwq=mul(qwq,qwq,x);
}
return 0;
}
bool ispri(int x) {
if(x<2) return 0;
for(int i=0; i<mx; ++i) {
if(x==pi[i]) return 1;
if(x%pi[i]==0) return 0;
if(!mr(x,pi[i])) return 0;
}
return 1;
}
signed main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
cin >> t;
while(t--) {
cin >> n;
if(ispri(n)) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}