这是 70 分的
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int Prime[7] = {2, 3, 5, 7, 11, 13, 37};
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
template <class T>
T randint(T l, T r = 0) {
static mt19937 eng(time(0));
if (l > r)
swap(l, r);
uniform_int_distribution<T> dis(l, r);
return dis(eng);
}
int Qpow(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p, b >>= 1;
}
return res;
}
bool Miller_Rabin(int x, int b) {
int d = x - 1, r = 0;
while (!(d & 1)) d >>= 1, r++;
int k = Qpow(b, d, x);
if (k == 1) return true;
for (int i = 0; i < r; ++i) {
if (k == x - 1) return true;
k = k * k % x;
}
return false;
}
bool isP(int x) {
if (x <= 1) return false;
for (int i = 0; i < 7; ++i) {
if (x == Prime[i]) return true;
if (x % Prime[i] == 0) return false;
if (!Miller_Rabin(x, Prime[i])) return false;
}
return true;
}
int f(int x, int c, int p) {return ((__int128)x * x + c) % p;}
int Pollard_Rho(int x) {
if (x == 4) return 2;
if (isP(x)) return x;
while (1) {
int c = randint <int> (1, x - 1);
int t = 0, r = 0, p = 1, q;
do {
for (int i = 0; (t = f(t, c, x), r = f(f(r, c, x), c, x)), i < 128; ++i) {
if (t == r or (q = (__int128)p * abs(t - r) % x) == 0) break;
p = q;
}
int d = gcd(p, x);
if (d > 1) return d;
} while (t != r);
}
}
int Find(int x) {
int fac = Pollard_Rho(x);
if (fac == x) return x;
else return max(Find(fac), Find(x / fac));
}
void solve() {
int n; cin >> n;
int k = Find(n);
if (k == n) puts("Prime");
else cout << k << '\n';
}
signed main() {
int T; cin >> T;
while (T--) solve();
return 0;
}
```
by isitover @ 2023-05-31 21:29:21
@[Quick_tky_Kk](/user/558743) 把 DILL 改成 `__int128` 就 80pts 了。不过有一些 WA。
by QAQ__ @ 2023-06-01 21:22:42
@[Quick_tky_Kk](/user/558743) 把你的 MR 换成我的就 90pts 了，应该 MR 也错了。
by QAQ__ @ 2023-06-01 21:26:42