Product

以下の条件を全て満たす $a,b$ の組を一つ求める問題です。

• $a \times b = N$
• $2 \leq a$
• $2 \leq b$
• $a,b$ は整数

そのような $a,b$ の組が存在するとき、$\min(a,b)$ の上限を見積もってみましょう。
これは、$\min(a,b) \leq \lfloor \sqrt{N} \rfloor$ です。 これは、以下のように証明できます。

任意の正整数 $1 \leq N \leq 10^{12}$ に対して、 $a \times b = N$ かつ $a,b \geq 2$ を満たす整数組 $a,b$ が存在するとします。このとき、$\min(a,b) \leq \lfloor \sqrt{N} \rfloor$ であることを証明します。

証明

1. 仮に $\min(a,b) > \sqrt{N}$ と仮定します。すると、 $a > \sqrt{N}$ かつ $b > \sqrt{N}$ となります。
2. この場合、 $a \times b > \sqrt{N} \times \sqrt{N} = N$ となります。しかし、これは $a \times b = N$ に矛盾します。
3. 矛盾が生じたため、仮定が間違っていることが分かります。したがって、 $\min(a,b) \leq \sqrt{N}$となります。
4. $\min(a,b)$ は整数であるため、$\min(a,b) \leq \lfloor \sqrt{N} \rfloor$ が成り立ちます。

以上より、$1 \leq N \leq 10^{12}$ 、 $a \times b = N$ 、 $a,b \geq 2$ を満たす $a,b$ に対して、 $\min(a,b) \leq \lfloor \sqrt{N} \rfloor$ であることが証明されました。

よって、$a \leq b$ としたとき、 $a$ の取りうる値の範囲は、$2 \leq a \leq \lfloor \sqrt{N} \rfloor$ であることが分かります。また、 $a$ を決めたとき、条件を全て満たす $b$ が存在するかは、 $N = 0 \mod a$ を満たすかで判定できます。

これより、$2 \leq a \leq \lfloor \sqrt{N} \rfloor$ の範囲で $a$ を全探索することで、この問題に正解できます。
計算量は $O(\sqrt{N})$ で十分高速です。

以下に Python の実装例を示します。