公式解説にもあるように、相異なる素数 \(p, q\) を用いて \(p^{8}\) もしくは \(p^{2}q^{2}\) と表せるものが答えです。

これらはどちらも平方数です。(一般に、正の約数の数が奇数であることと平方数であることは同値です。)

よって、\(\sqrt{N}\) 以下の整数全てに対して素因数分解をして、それらが \(p^{4}\) もしくは \(pq\) という形で表せるかを判断したら良いです。

\(p^{4}\) であることは約数の数が \(5\) 個であることと同値です。

\(pq\) であることは約数の数が \(4\) 個かつ、\(1\) でも \(pq\) でもない二つの素数が互いに素であることと同値です。

これを実装すれば良いです。

実装例 c++ 1420ms

とても遅いです。なぜなら、時間/空間計算量ともに \(O(\sqrt{N}\log{N})\) であるからです。実際にはそれぞれの数について、以下の値があれば判定ができます。

• 最小の素因数
• 約数の数

よって、空間計算量が \(\Theta(\sqrt{N})\) に抑えられます。

実装例 c++ 96ms