平方数の判定をするアルゴリズム

数学全探索, 素因数分解, 約数の個数, 平方数, 平方根

Nが自然数の2乗で表現できるとき、平方数と言います。

  • 平方数の例
    • 4 (= 2×2)
    • 9 (= 3×3)
    • 16 (= 4×4)
    • 25 (= 5×5)

アルゴリズム

全探索でのアルゴリズム:

  1. \(\sqrt{N}\) 以下の自然数 \(k\) に対して以下を確かめる
    • \(k^2 = N\) となる \(k\) が存在すれば N は平方数

※ 平方数なら、\(k^2 = N\) となる \(\sqrt{N}\) 以下の自然数 \(k\) が必ず存在するので、それを探索します。

約数の個数を利用したアルゴリズム:

  1. Nの約数の個数を求める
  2. 約数の個数が奇数なら平方数、偶数なら平方数ではない。

※ 約数の個数の求め方については、こちらを参照してください。

※ 奇数か偶数かの判定は、2 で割り切れるかどうかを確認すればよいです。

※ 平方数の約数の個数は必ず奇数になります。以下は平方数 36 の約数を並べた時の図です。

平方数の約数は必ず奇数

平方根を利用したアルゴリズム:

  1. N の平方根 r を計算する
  2. r を「切り捨て or 切り上げ or 四捨五入」した数を2乗する。これがNに一致すれば平方数、一致しなければ平方数ではない。

※ 平方数なら r は必ず整数なので「切り捨て or 切り上げ or 四捨五入」のどれを行っても r が変化しません。平方数でなければ r が小数から整数になるので必ず変化してしまいます。

※ 例えば、36 の平方根は 6 で、これは「切り捨て or 切り上げ or 四捨五入」のどれを行っても 6 のままです。2乗すると 36 に一致します。

計算量

全探索でのアルゴリズム

  • \(O(\sqrt{N})\)

全ての \(\sqrt{N}\) 以下の自然数 \(k\) を確かめることになるので、全体としては \(O(\sqrt{N})\) になります。

約数の個数を利用したアルゴリズム

  • 前処理なしのアルゴリズム
    • 前処理:なし
    • クエリ:\(O(\sqrt{N})\)
  • 前処理ありのアルゴリズム
    • 前処理:\(O(N \log \log N)\)
    • クエリ:\(O(\log N)\)

約数の個数をどのように求めるかで計算量が変わってきます。(詳細:Nの約数の個数を求めるアルゴリズム

奇数か偶数かの判定は \(O(1)\) でできるので、全体には影響しません。

平方根を利用したアルゴリズム

一般的には約数の個数を利用したアルゴリズムよりも高速です。

計算量は平方根をどれだけの速度で計算できるかによって変化します。コンピュータによって違うこともありますし、プログラミング言語でサポートされている sqrt() 関数の速度にも依ります。

C++ での実装例

約数の個数を利用したアルゴリズム

約数の個数を求めるために、素因数分解を利用しています。前処理はしていません。

平方根を利用したアルゴリズム

整数で計算するか、浮動小数点で計算するか注意する必要があります。

平方根を計算する時は浮動小数点で計算する必要がありますが、切り捨て・切り上げ・四捨五入などを行ったら整数型にして計算するのが良いでしょう。

練習問題