大概率不是 Miller Rabin 测多了的问题。

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 100010;
ll n, fac;
ll pri[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

ll smul (ll a, ll b, ll mod)
{
    ll ad = 0, bs = a;
    while (b)
    {
        if (b & 1)
            ad = (ad + bs) % mod;
        bs = (bs + bs) % mod;
        b >>= 1;
    }
    return ad;
}

ll qpow (ll a, ll b, ll mod)
{
    ll ml = 1, bs = a;
    while (b)
    {
        if (b & 1)
            ml = smul (ml, bs, mod) % mod;
        bs = smul (bs, bs, mod) % mod;
        b >>= 1;
    }
    return ml % mod;
}

bool Miller_Rabin (ll n)
{
    for (int i = 1; i <= 11; i++)
    {
        if (n == pri[i])
            return 1;
    }
    if (n < pri[11])
        return 0;
    ll d = n - 1, r = 0;
    while ((d & 1) == 0)
    {
        d >>= 1;
        r++;
    }
    for (int i = 1; i <= 11; i++)
    {
        if (n % pri[i] == 0)
            return 0;
        ll p = qpow (pri[i], d, n);
        ll q = p;
        for (int j = 0; j < r; j++)
        {
            p = smul (p, p, n);
            if (p == 1)
            {
                if (q != 1 && q != n - 1)
                    return 0;
                else
                    break;
            }
            q = p;
        }
        if (p != 1)
            return 0;
    }
    return 1;
}

ll gcd (ll a, ll b)
{
    return (!b ? a : gcd (b, a % b));
}

ll Pollard_Rho (ll n)
{
    if (n == 4)
        return 2;
    if (Miller_Rabin (n))
        return n;
    while (1)
    {
        ll c = rand() % (n - 1) + 1;
        auto f = [=](ll x){return (smul (x, x, n) + c) % n;};
        ll t = 0, r = 0, p = 1, q;
        do
        {
            for (int i = 0; i < 128; i++)
            {
                t = f(t);
                r = f(f(r));
                if (t == r)
                    break;
                if ((q = smul (p, abs (t - r), n)) == 0)
                    break;
                p = q;
            }
            ll d = gcd (p, n);
            if (d > 1)
                return d;
        } while (t != r);
    }
}

void max_factor (ll n)
{
    // printf ("%lld - %lld\n", n, fac);
    if (n <= fac || n < 2)
        return;
    if (Miller_Rabin (n))
        fac = max (fac, n);
    ll p = Pollard_Rho (n);
    while (n % p == 0)
        n /= p;
    max_factor (n);
    max_factor (p);
}

int main()
{
    int T;
    scanf ("%d", &T);
    while (T--)
    {
        scanf ("%lld", &n);
        fac = 0;
        max_factor (n);
        if (fac == n)
            puts ("Prime");
        else
            printf ("%lld\n", fac);
            // puts ("Not Prime");
    }
    return 0;
}