算法1

(Miller Rabin) $O(log n)$

我们知道，除了 $2$ 以外，其他的质数都是奇质数。而 $2$ 我们可以直接判断，其他的质数 $p$，减一后一定为偶数。

众所周知，一个偶数肯定能表达为 $2^r \cdot d$ 的形式。

那柿子就变为了 $(a \cdot d)^{2^r} \equiv 1 \pmod{p}$，但它的逆命题不一定成立——

所以判断的时候只用费马小定理是不行滴！有些数字满足费马小定理，但是并不是质数（例如：$2305843009213693951$）这些偷奸耍滑的数被称作伪素数。

于是，我们需要第二次探测......

二次探测定理

若 $p$ 为素数，∃x, 0 < x < p，则方程 $x^2 \equiv 1 \pmod{p}$ 的解只能为 1 或 $p-1$。

证明：

$x^2 \equiv 1 \pmod{p}$

⇓

$x^2 - 1 \equiv 0 \pmod{p}$

根据平方差公式，可得

$x^2 - 1 \equiv (x + 1)(x - 1) \equiv 0 \pmod{p}$

因为 $p$ 为一个质数，所以 $(x + 1)(x - 1)$ 要么等于 0，要么等于 $p$ 的倍数。

若 $(x + 1)(x - 1) = 0$，则 $x = 1$。

若 $p \mid (x + 1)(x - 1)$，则 $x = p - 1$ 或 $x = p + 1$，但 $p + 1 > p$ 不符合要求，所以这种条件下符合条件的解只有 $x = p - 1$。

综上，$x$ 的解只能为 1 或 $p - 1$。

好了，主题思路就是随机取一个值进行探测，探测次数不要太多也不要太少，经过费马小定理和二次探测，就可以大概率的判断是否为质了（出错的概率非常小，比现在你的电脑突然爆炸的几率还要小，所以我们默认探测是对的，请放心食用）。

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
LL prime[15]={2,3,5,13,17,31,37};
LL qmi(LL a,LL b,LL p)
{
    LL res=1;
    while(b)
    {
        if(b&1)res=(__int128)res*a%p;
        a=(__int128)a*a%p;
        b>>=1;
    }
    return res;
}
bool M_R(LL n,LL a)
{
    LL d=n-1,r=0;
    while(!(d&1))
    {
        d>>=1;
        r++;
    }
    LL k=qmi(a,d,n);
    if(k==1)return true;
    for(int i=0;i<r;i++)
    {
        if(k==n-1)return true;
        k=(__int128)k*k%n;
    }
    return false;
}
bool isprime(LL n)
{
    if(n<=1)return false;
    for(int i=0;i<7;i++)
    {
        if(n==prime[i])return true;
        if(n%prime[i]==0)return false;
        if(!M_R(n,prime[i]))return false;
    }
    return true;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        LL n;
        scanf("%lld",&n);
        if(isprime(n))puts("Yes");
        else puts("No");
    }
    return 0;
}