整数 \(M\) が素数 \(p_1,\ldots,p_k\) を用いて \(p_1^{r_1}\times p_2^{r2}\times \ldots\times p_k^{r_k}\) と素因数分解されるとき、\(M\) の約数の個数は \((r_1+1)(r_2+1)\ldots(r_k+1)\) となることが知られています。

この事実を用いると、素数 \(p\) を用いて \(p^8\) と表される正整数のうち \(N\) 以下のものの個数と、異なる素数 \(p,q\) を用いて \(p^2q^2\) と表される正整数のうち \(N\) 以下のものの個数が分かればよいです。

まず、前者は簡単です。素数を小さい順に見ていき、\(8\) 乗が \(N\) を超えたところで打ち切ればよいです。

後者について考えます。まず、\(p,q\) については \(\mathrm{O}(\sqrt{N})\) 以下の素数のみ考えればよいです。

\(p\) を昇順に全探索していきます。このとき、\(p^2q^2\leq N\) なる \(q\) の最大値は単調に減少していくので、尺取り法を用いることで、\(\mathrm{O}(\sqrt{N})\) 以下の素数の個数に対して線形時間でこの問題を解くことが出来ます。