\(a, b\) を素因数分解して, べき乗数が奇数である素因数列が一致すれば \(ab\) は平方数となる.

そこで, エラトステネスの篩で素数を見付けていき, 見つかった素数 \(p\) について \(1\) から \(N\) までの数値が入ったテーブルの \(p^2\) の倍数番目の数値を \(p^2\) で割れるだけ割る.

こうしてテーブルに残った数値が同じ数値同士は掛けると平方数になるので, 同じ数値同士のグループに含まれる要素数を数え上げ, 各グループの要素数の2乗和が答えとなる.