更好的isprime

题目描述

传统的判断素数的方式都是从 $2$ 枚举到 $\lfloor \sqrt{n} \rfloor$，试图寻找 $n$ 的因数，如果找不到则说明 $n$ 是素数。这种方法判断素数的时间复杂度是 $\mathrm{O}(\sqrt{n})$，那我们能不能做的更好呢？

Miller-Rabin 素性测试，是一种基于二次探测定理和费马小定理的，用于快速测试一个奇数是否是素数的方法，对 $n$ 进行一次 Miller-Rabin 素性测试的时间复杂度仅为 $\mathrm{O}(\log n) $。通过素性测试的数不一定是素数，可是没通过素性测试的数一定不是素数。用不同的数作为基底对 $n$ 进行多次素性测试，可以使得通过了这些素性测试的 $n$ 是素数的概率尽可能大。

不过对于范围 $[1,2^{32})$ 的数字，只要它能分别通过 $2,7,61$ 这三个数为基底的 Miller-Rabin 素性测试，它就一定是素数。

下面给出进行 Miller-Rabin 素性测试的代码，请你调用 Miller-Rabin 素性测试函数实现一个更好的 isprime 函数，并调用 isprime 函数完成本题要求。

int qpow(int a, long long n, int mod) // 这只是一个快速幂，你可以不用管它
{
    int ans = 1;
    int base = a;
    while (n > 0)
    {
        if (n & 1)
        {
            ans = ans * (long long)base % mod;
        }
        base = (long long)base * base % mod;
        n >>= 1;
    }
    return ans;
}

/* 如果通过素性测试，那么下面这个函数返回1，否则返回0 */
int Miller_Rabin_check(int a, int n) // a是基底，n是你拿来进行素性测试的数
{
    int u = n - 1;
    while (u % 2 == 0)
    {
        u /= 2;
    }
    int v = qpow(a, u, n);
    if (v == 1)
        return 1;
    while (u <= n - 1)
    {
        if (v == n - 1)
            return 1;
        if (v == 1)
            return 0;
        v = 1ll * v * v % n;
        u *= 2;
    }
    return 0;
}
int isprime(int n)
{
    if (n == 2 || n == 7 || n == 61) // 作为基底的这三个数需要特殊处理
        return 1;
    /* 补全你的代码 */
}

输入

第一行一个正整数 $t$ 表示数据组数，$1\le t \le 3 \times 10^5$。

接下来 $t$ 行，每行一个正整数 $n$，$2 \le n \le 10^9$。

输出

对于每组数据，如果 $n$ 是素数，输出 Yes，否则输出 No。

输入样例

6
2
61
47
1145
1919810
998244353

输出样例

Yes
Yes
Yes
No
No
Yes

Not Hint

如果你实在很闲可以看看原理