费马素性检验

由费马小定理，如果 $p$ 为质数并且 $\left(a,p\right)=1$，那么 $a^{p-1}\equiv 1 \left(\text{mod}\ p\right)$。那么，如果 $a^{p-1}\not\equiv 1 \left(\text{mod}\ p\right)$，那么 $p$ 就一定不是素数。因此，我们只要多试几个数，如果 $a^{p-1}\equiv 1 \left(\text{mod}\ p\right)$ 都成立，那么 $p$ 大概率就是素数。

但仍旧存在极少的一些合数，即便遍历 $\left[2,p-1\right]$ 的每一个数字作为底数，也无法筛去。这样的合数被称为卡迈克尔数，在一亿内有 $255$ 个，最小的卡迈克尔数为 $561$。若 $n$ 为卡迈克尔数，则 $2^n-1$ 也是卡迈克尔数，故其个数是无穷的。

因此，我们要考虑其他的方法。

二次探测

如果 $p$ 为质数，那么方程 $x^2\equiv 1\left(\text{mod} p\right)$ 只有 2 个解($x_1=1,x_2=p-1$)。

证明：因为 $p$ 为质数，又 $p|(x-1)(x+1)$，则 $p|x-1$ 或 $p|x+1$，所以 $x=1$ 或 $x=p-1$。

这样子，事先判定掉偶数的情况。$p$ 为奇数时，$a^{p-1}=\left(a^\frac{p-1}{2}\right)^2\equiv 1\left(\text{mod} p\right)$。因此，我们可以通过判断 $a^\frac{p-1}{2}$ 是否是 $1$ 和 $p-1$ 中的一个来判断 $p$ 是否为质数。同样的，这只是必要条件。我们可以通过多次判断来降低错误概率。

代码

C++代码

#include <cstdio>
#include <cstring>
#include <algorithm>

#define RI register int

using namespace std;

int prime[21]= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 79};

inline int Quick_Multiply(int a, int b, int c) {
    long long ans = 0, res = a;
    while (b) {
        if (b & 1)
            ans = (ans + res) % c;
        res = (res + res) % c;
        b >>= 1;
    }
    return (int)ans;
}
int Quick_Power(int a, int b, int c) {
    int ans= 1, res = a;
    while (b) {
        if(b & 1)
            ans = Quick_Multiply(ans, res, c);
        res = Quick_Multiply(res, res, c);
        b >>= 1;
    }
    return ans;
}
bool Miller_Rabin(int x) {
    int s = 0, t = x - 1, k;
    if (x==2) 
        return 1;
    if (x < 2 || !(x & 1))
        return 0;
    while(!(t & 1)) {
        s++;
        t >>= 1;
    }
    for(RI i = 0; i < 1 && prime[i] < x; ++i) {
        int a = prime[i];
        int b = Quick_Power(a, t, x);
        for(RI j = 1; j <= s; ++j) {
            k = Quick_Multiply(b, b, x);
            if (k == 1 && b != 1 && b != x - 1)
                return 0;
            b = k;
        }
        if(b != 1)
            return 0;
    }
    return 1;
}
int main() {
    int x;
    int n, m;
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d", &x);
        if(Miller_Rabin(x)) 
            printf("Yes\n");
        else 
            printf("No\n");
    }
    return 0;
}