\(N = p^{2} q \leq 9*10^{18}\) と \(N\) が大きいが， 素因数の最小値は小さい． (重複を許して)3つの素因数があるので，どれか一つは\(N^{1/3}\) 以下． よって， \(min(p,q)\) のうち，一方は全探索で求まる． \(p,q\) の一方が求まれば，もう一方も求まる．
クエリ問題なので，使われる素数を前計算して使いまわしたが， \(T \leq 10\) だったのでクエリごとに計算しなおしても間に合う．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// エラトステネスの篩
template<typename T>
isPrime[0] = false;
isPrime[1] = false;
for (T i = 2; i <= n; i++ )
{
if ( !isPrime[i] ) continue;
T a = 2*i; // i の倍数
while( a <= n ){
isPrime[a] = false;
a += i;
}
}
return isPrime;
}
int main() {
ll t; cin >> t;
vll a;
rep(i,v.size()) if(i >= 2){
if(v[i]) a.push_back(i);
}
rep(ti,t){
ll n; cin >> n;
ll p = -1,q = -1;
ll x = -1;
for(auto i:a){
if(n%i==0){
x = i;
break;
}
}
assert(x > 0);
n /= x;
if(n % x == 0) {
p = x;
q = n/x;
}else{
q = x;
p = sqrt(n);
}
cout << p << " " << q << endl;
}
return 0;
}
