与えられた整数 \(N\) を素因数分解するアルゴリズムとしては、\(i=1,2,\dots,\lfloor\sqrt{N}\rfloor\) の順に \(N\) が \(i\) で割り切れるかどうかを確かめる \(O(\sqrt{N})\) のアルゴリズムが有名です (試し割りと呼ばれることが多いです)。

なぜ \(\lfloor\sqrt{N}\rfloor\) まで試し割りするだけで良いのか

\(N\) を \(\lfloor\sqrt{N}\rfloor\) 以下の素因数で割り切れるだけ割って、残った数を \(N'\) とします。\(N'=1\) の場合は既に全ての素因数を見つけたということなので、\(N' > 1\) の場合を考えます。ここで、\(N'\) は \(\lfloor\sqrt{N}\rfloor+1\) 以上の素因数しか持ち得ないこと、\(\lfloor\sqrt{N}\rfloor+1\) 以上の数を \(2\) つ以上掛け合わせると \(N\) を超えてしまう (明らかに \({N'} \leq N\) なので、\(N'\) が \(2\) つ以上の素因数を持つと仮定すると矛盾が生じます) ことから、\(N'\) は素数であることがわかります。よって、最初の試し割りで見つけた素因数と合わせることで素因数分解が完了します。

しかし、本問題では \(N\) が大きいため、\(O(\sqrt{N})\) の試し割りは間に合いません。そこで、\(N=p^2q\) (\(p,q\) は素数) と表せるという条件を使います。

重要な性質として、 \(\min(p,q)\leq\sqrt[3]{N}\) が成り立ちます (これが成り立たないと仮定すると、\(p^2q>N\) となって矛盾します)。よって、\(\sqrt{N}\) まで試し割りしなくとも、\(\sqrt[3]{N}\) まで試し割りすれば \(p\) と \(q\) のうち少なくとも一方は見つかることがわかります。この方針の下、以下のように具体的なアルゴリズムを構築可能です。

1. \(i=1,2,\dots,\lfloor\sqrt[3]{N}\rfloor\) のうち、\(N\) が \(i\) で割り切れるような最大の \(i\) を \(A\) とおく (\(A=p\) または \(A=q\) である)。
2. \(\frac{N}{A}\) が \(A\) で割り切れるか調べる。割り切れるなら、\(p=A,q = \frac{N}{A^2}\) である。割り切れないなら、\(p = \sqrt{\frac{N}{A}},q=A\) である。

よって、\(1\) テストケースあたり \(O(\sqrt[3]{N})\) でこの問題を解くことができました。

なお、Pollard’s rho algorithm などの高速な素因数分解アルゴリズムを用いることでもこの問題を解くことができます。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        
        ll p = 0, q = 0;
        for (ll i = 2; i * i * i <= n; i++) {
            if (n % i != 0) continue;
            if ((n / i) % i == 0) {
                p = i;
                q = n / i / i;
            } else {
                q = i;
                p = (ll) round(sqrt(n / i));
            }
            break;
        }
        cout << p << ' ' << q << endl;
    }
}