首先给出两个定理：
1.费马小定理
设p是一个素数，a是一个整数，且不是p的倍数，那么
(a^{p−1} equiv 1 pmod p)
2.二次探测定理
若(p)是素数，(x)是一个正整数，且(x^2 mod p = 1)，那么(x equiv pm 1 pmod p)
QwQ经过验证，发现费马小定理的逆定理是不成立的，但是，我们可以运用费马小定理的逆否命题来筛掉一些素数，然后接着用二次探测定理来筛
设被测的数为n，取一个比n小的正整数a，设(n-1=d imes 2^r)，若n是素数，则要么(a^d mod n = 1)，要么存在一个i，满足(0 le i < r)且$a^{d imes 2^i} mod n = -1 $
算法实现的过程大致是：
对于要判断的数n
1.先判断是不是2，是的话就返回true。
2.判断是不是小于2的，或合数，是的话就返回false。
3.令n-1=u*2^t，求出u，t，其中u是奇数。
4.听亢神的话，将a选为2,7,61,24251就可以了！
根据费马小定理，如果a^(n-1)≡1(mod p)那么n就极有可能是素数，如果等式不成立，那肯定不是素数了
因为n-1=u*2t，所以a(n-1)=a(u*2t)=(au)(2^t)。
5.所以我们令x=(a^u)%n
6.然后是t次循环，每次循环都让y=(x*x)%n，x=y,这样t次循环之后x=a(u*2t)=a^(n-1)了
7.因为循环的时候y=(x*x)%n，且x肯定是小于n的，正好可以用二次探测定理，
如果(x^2)%n1，也就是y等于1的时候，假如n是素数，那么x1||x==n-1，如果x!=1&&x!=n-1，那么n肯定不是素数了，返回false。
8.运行到这里的时候x=a^(n-1)，根据费马小定理，x!=1的话，肯定不是素数了，返回false
对每一个上述的底数，都做一遍 就可以了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
ll a,k[10];
ll qsc(ll i,ll j,ll mod)
{
ll ans=0;
while (j)
{
if (j&1) ans=(ans+i)%mod;
i=(i+i)%mod;
j>>=1;
}
return ans;
}
ll qsm(ll i,ll j,ll mod)
{
ll ans=1;
while (j)
{
if (j&1) ans=(ans*i)%mod;
i=(i*i)%mod;
j>>=1;
}
return ans;
}
int t;
int n,m;
bool miller_rabin(ll x)
{
if (x==2 || x==7 || x==61 || x==24251) return true;
if (x==1) return false;
ll t = x-1,mi=0; //将x-1分解成t*2^mi
while (!(t&1))
{
t>>=1;
mi++;
}
for (int i=1;i<=4;i++)
{
ll a=k[i];
ll ymh = qsm(a,t,x); //a^t
for (int j=1;j<=mi;j++)
{
ll front = ymh;//ymh
ymh=qsc(ymh,ymh,x);//ymh^2 这里运用了二次探测定理
if (ymh==1 && front!=1 && front!=x-1) return false;
}
if (ymh!=1) return false; //费马小定理的逆否命题
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);
k[1]=2;
k[2]=7;
k[3]=61;
k[4]=24251;
while (m--)
{
ll x;
scanf("%lld",&x);
if (miller_rabin(x)) printf("Yes
");
else printf("No
");
}
return 0;
}