题意：是素数就输出Prime，不是就输出最小因子.
#include <cstdio>
#include<time.h>
#include <algorithm>
#include<set>
using namespace std; typedef long long llt; int const Repeat = ;
set<llt>sss;
//利用二进制计算a*b%mod
llt multiMod(llt a, llt b, llt mod){
llt ret = 0LL;
a %= mod;
while (b){
if (b & 1LL) ret = (ret + a) % mod, --b;
b >>= 1LL;
a = (a + a) % mod;
}
return ret;
} //计算a^b%mod
llt powerMod(llt a, llt b, llt mod){
llt ret = 1LL;
a %= mod;
while (b){
if (b & 1LL) ret = multiMod(ret, a, mod), --b;
b >>= 1LL;
a = multiMod(a, a, mod);
}
return ret;
} //Miller-Rabin测试,测试n是否为素数
bool Miller_Rabin(llt n, int repeat){
if (2LL == n || 3LL == n) return true;
if (!(n & 1LL)) return false; //将n分解为2^s*d
llt d = n - 1LL;
int s = ;
while (!(d & 1LL)) ++s, d >>= 1LL; //srand((unsigned)time(0));
for (int i = ; i<repeat; ++i){//重复repeat次
llt a = rand() % (n - ) + ;//取一个随机数,[2,n-1)
llt x = powerMod(a, d, n);
llt y = 0LL;
for (int j = ; j<s; ++j){
y = multiMod(x, x, n);
if (1LL == y && 1LL != x && n - 1LL != x) return false;
x = y;
}
if (1LL != y) return false;
}
return true;
} llt Fac[];//质因数分解结果（刚返回时是无序的）
int FCnt;//质因数的个数。数组小标从0开始 llt gcd(llt a, llt b){
if (0L == a || 0L == b) return ;
if (a < ) a = -a;
if (b < ) b = -b;
while (b){
llt t = a % b;
a = b;
b = t;
}
return a;
}
llt Pollard_Rho(llt n, llt c){
llt i = , k = ;
llt x = rand() % n;
llt y = x;
while (){
++i;
x = (multiMod(x, x, n) + c) % n;
llt d = gcd(y - x, n);
if (d != 1LL && d != n) return d;
if (y == x) return n;
if (i == k) y = x, k <<= ;
}
} void find(llt n){
if (4LL == n){
Fac[] = Fac[] = 2LL;
FCnt = ;
return;
}
if (Miller_Rabin(n, Repeat)){
Fac[FCnt++] = n;
return;
} llt p;
while ((p = Pollard_Rho(n, rand() % (n - ) + )) == n); find(p);
find(n / p);
} int main(){
int kase;
scanf("%d", &kase);
while (kase--){
llt n;
scanf("%lld", &n); FCnt = ;
if (Miller_Rabin(n, )){ printf("Prime\n"); }
else{
find(n);
llt ans = Fac[];
for (int i = ; i < FCnt;++i)
if (ans>Fac[i])ans = Fac[i];
printf("%lld\n", ans);
}
}
return ;
}