Pythonでsqrt関数を使わずに数が完全平方数かどうかを判定するプログラム

ある整数 n が与えられたとき、n が完全平方数（perfect square）かどうかを判定する問題を考えます。完全平方数とは、ある整数 a を用いて k = a × a と表せる数のことです。この問題は、Pythonの組み込み平方根関数（math.sqrt など）を一切使わずに解く必要があります。

例えば、入力が n = 121 の場合、121 = 11 × 11 と表せるため、出力は True になります。

解き方のアプローチ：二分探索

平方根関数を使わずに判定するには、二分探索（バイナリサーチ）を活用するのが効率的です。候補となる数の範囲を半分ずつ絞り込んでいくことで、高速に答えを見つけられます。

具体的な手順は以下の通りです。

• n が 0 または 1 の場合

  • True を返します（0 = 0×0、1 = 1×1 なので完全平方数です）

• start := 2 とします

• stop := n / 2 の切り捨て値とします

• start ≤ stop の間、以下を繰り返します

  • temp := start から stop までのすべての数のリスト

  • k := temp の中央の要素

  • k_squared := k × k

  • k_squared が n と等しければ

    • True を返します

  • k_squared が n より大きければ

    • start := temp[0]

    • stop := k − 1

  • そうでなければ

    • start := k + 1

    • stop := temp の最後の要素

• ループが終了したら False を返します

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(n):
    if n == 0 or n == 1:
        return True
    start = 2
    stop = n // 2
    while start <= stop:
        temp = range(start, stop + 1)
        k = temp[len(temp) // 2]
        k_squared = k * k

        if k_squared == n:
            return True

        if k_squared > n:
            start = temp[0]
            stop = k - 1
        else:
            start = k + 1
            stop = temp[-1]

    return False

n = 121
print(solve(n))

入力

121

出力

True

処理の流れと計算量

このアルゴリズムでは、探索範囲を毎回半分に絞り込むため、時間計算量は O(log n) となります。単純に 2 から n/2 まで順番に全数チェックする方法（O(n)）と比べて、大きな数に対しても非常に高速に動作するのが特徴です。

なお、n が 4 以上の場合、その平方根は必ず n/2 以下になるため、探索範囲の上限を n // 2 としても答えに影響しません。また、負の数は完全平方数になり得ない点にも注意してください。