一次探测

由费马小定理得当 $p$ 是质数且 $a$ ， $p$ 互质时由 $a^{p-1}\equiv1(mod\ p)$ ，取前 $12$ 个素数做 $a$ 依次判断是否符合

二次探测

对质数 $p$ 方程 $x^2\equiv1(mod\ p)$ 只有 $1$ 和 $p-1$ （ $-1$ ）两个解，由于已知 $a^{p-1}\equiv1$ ，求 $a^{\frac{p-1} 2}$ 的值，如果不是 $1$ 或 $p-1$ ，则是合数。如果是，计算 $a^{\frac{p-1} 4}$ 直到指数是奇数。

特判

$1$ ， $2$ ，还有就是测试的质数的情况。

代码

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll n,m;

inline ll read()

{

	register ll res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

ll prime[12] = {2ll,3ll,5ll,7ll,11ll,13ll,17ll,19ll,23ll,29ll,31ll,37ll};

inline ll mul(ll a,ll b,ll mod)

{

	register ll res = 0ll;

	a %= mod;

	while(b)

	{

		if(b & 1)res = (res + a) % mod;

		a = (a << 1) % mod;

		b = b >> 1;

	}

	return res;

}

inline ll power(ll a,ll b,ll mod)

{

	register ll res = 1ll;

	a %= mod;

	while(b)

	{

		if(b & 1ll)res = mul(res,a,mod);

		b = b >> 1;

		a = mul(a,a,mod);

	}

	return res;

}

bool check(ll a,ll b,ll mod)

{

	if((b & 1) == 1)return true;

	register ll t = power(a,(b >> 1),mod);

	if(t == 1ll)return check(a,(b >> 1),mod);

	else if(t == mod - 1ll)return true;

	else return false;

}

inline bool test(ll k)

{

	if(k == 1)return false;

	if(k == 2ll)return true;

	if((k & 1ll) == 0)return false;

	for(register int i = 0;i < 9;++i)

	{

		if(prime[i] == k)return true;

		else if(power(prime[i],k - 1ll,k) != 1ll)return false;

		else if(!check(prime[i],k - 1ll,k))return false;

	}

	return true;

}

int main()

{

	n = read();m = read();

	for(register int i = 1;i <= m;++i)

	{

		if(test(read()))puts("Yes");

		else puts("No");

	}

	return 0;

}