rt,求助，不知道哪里T掉过不去

感觉写法没有问题，不知道是常数问题还是写法问题

实测判质数的地方加上线性筛一部分范围的质数会会优大概1s左右，但仍然无法通过最后一个点

求助/kk

#include <bits/stdc++.h>
#include <random>
#define int long long
using namespace std;

const int SIZE = 1e6 + 5, siz = 1e6;

int tot;
int isPri[SIZE], pri[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using GTR::read;

int t, n, ans;
mt19937 myrand(time(NULL));

int qPow(int a, int b, int mod) {
	int ans = 1;
	for ( ; b; b >>= 1, a = a * a % mod) {
		if (b & 1) ans = ans * a % mod;
	}
	return ans;
}

inline int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
inline int qMul(int a, int b, int p) {
		int r = a * b - (int) ((long double) a * b / p + 0.5) * p; return r < 0 ? r + p : r;
}
inline bool test(int a, int p) { return qPow(a, p - 1, p) == 1; }

bool mR(int x, int p) {
	if (x <= siz && isPri[x]) return 0;
	if (!test(x, p)) return 0;
	int k = p - 1;
	while (!(k & 1)) {
		k >>= 1; int tmp = qPow(x, k, p);
		if (tmp != 1 && tmp != p - 1) return 0;
		if (tmp == p - 1) return 1;
	}
	return 1;
}

bool isPrime(int p) {
	if (p == 1 || p == 46856248255981 || (p <= siz && isPri[p])) return 0;
	if (p <= siz && !isPri[p]) return 1;
	return mR(2, p) && mR(61, p);
}

inline int f(int x, int c, int mod) { return (qMul(x, x, mod) + c) % mod; }

int pollardRho(int n) {
	int c = myrand() % (n - 1) + 1, t1 = 0, t2 = 0, tmp = 0;
	for (int s = 1, t = 2; ; s <<= 1, t <<= 1) {
		t2 = t1, tmp = 1;
		for (int i = s, cnt = 1; i < t; ++ i, ++ cnt) {
			t2 = f(t2, c, n), tmp = qMul(tmp, abs(t2 - t1), n);
			if (cnt == 127) {
				cnt = 0; int g = gcd(tmp, n);
				if (g > 1) return g;
			}
		}
		int g = gcd(tmp, n);
		if (g > 1) return g; t1 = t2;
	}
}

void getFac(int n) {
	if (ans >= n) return;
	if (n <= siz && !isPri[n]) return ans = std::max(ans, n), void();
	if (isPrime(n)) return ans = std::max(ans, n), void();
	if (n < 2) return;
	int g = n; while (g == n) g = pollardRho(n);
	getFac(g); getFac(n / g);
}

signed main() {
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	isPri[1] = 1;
	for (int i = 2; i <= siz; ++ i) {
		if (!isPri[i]) pri[++ tot] = i;
		for (int j = 1; j <= tot && i * pri[j] <= siz; ++ j) {
			isPri[i * pri[j]] = 1;
			if (!(i % pri[j])) break;
		}
	}
	t = read();
	while (t --) {
		n = read(), ans = 0;
		getFac(n);
		if (ans == n) puts("Prime");
		else printf("%lld\n", ans);
	}
	return 0;
}