問題は次のように言い換えられます：

\(1\) 以上 \(N\) 以下の整数 \(x\) で，\(x^{1/b}\) が整数となるような正整数 \(b\) の最大値が \(2\) 以上のものはいくつありますか？ ただし \(x=1\) も数え入れるものとします．

　次のように記号を定めます：

• \(2\) 以上の整数 \(x\) に対し，\(x^{1/b}\) が整数となるような正整数 \(b\) の最大値を \(g(x)\) とする．
• 正整数 \(n\) および \(2\) 以上の整数 \(k\) に対し，整数 \(x\ (\red{2}\leq x\leq n)\) のうち \(g(x)=k\) を満たすものの個数を \(f_k(n)\) とする．
• \(F(n)\coloneqq\sum_{k\geq 2}f_k(n)\)．

このとき元の問題の答えは \(1+F(N)\) です．

　整数 \(x\ (2\leq x\leq n)\) のうち \(x^{1/k}\) が整数となるものは

\[2^k,3^k,\dots,\lfloor n^{1/k}\rfloor^k\]

の \(\lfloor n^{1/k}\rfloor-1\) 個です． このような \(x\) に対して素因数分解を考えれば \(g(x)>k\iff g(x^{1/k})>1\) であるので，\(g(x)>k\) である \(x\) の総数は

\[2,3,\dots,\lfloor n^{1/k}\rfloor\]

のうち \(g(\cdot)>1\) であるものの総数，すなわち \(\sum_{l\geq 2}f_l(\lfloor n^{1/k}\rfloor)=F(\lfloor n^{1/k}\rfloor)\) と一致します． 従って次の等式が得られます：

\[f_k(n)=\lfloor n^{1/k}\rfloor-1-F(\lfloor n^{1/k}\rfloor)\]

これを \(k\geq 2\) に対して足し合わせれば次を得ます．

\[F(n)=\sum_{k\geq 2}\left(\lfloor n^{1/k}\rfloor-1-F(\lfloor n^{1/k}\rfloor)\right)\]

\(k>\log_2n\) ならば \(\lfloor n^{1/k}\rfloor=1\) であることと \(F(1)=0\) に注意すれば，上の式からメモ化再帰などで実装できます．

　計算量については \(F(N)\) を計算するために必要な値は \(F(\lfloor N^{1/k}\rfloor)\) の形のもののみなので \(O((\log N)^2)\) などになります．