C++で平方根を使わずに数値が完全平方数かどうかを判定する方法

数値が与えられたとき、その数が完全平方数（perfect square）かどうかを判定することを考えます。ここでは、平方根の演算を使用せずに判定を行う方法を紹介します。例えば、1024は 32 × 32 = 1024 と表せるため完全平方数ですが、1000はいかなる整数の二乗にもならないため完全平方数ではありません。

考え方は非常にシンプルです。1から順に整数 i を増やしながら、i × i が n を超えるまで調べます。このとき、n が i で割り切れ、かつ商（n ÷ i）も i と等しい場合、すなわち n = i × i が成立した時点で、n は完全平方数であると判定できます。

アルゴリズム

isPerfectSquare(n) −

入力 − 判定対象の数値 n

出力 − n が完全平方数であれば true、そうでなければ false

begin
    for i := 1, i² ≤ n, increase i by 1:
        if n is divisible by i, and n / i = i, then
            return true
    done
    return false
end

C++での実装例

#include <iostream>
using namespace std;
bool isPerfectSquare(int number) {
    for (int i = 1; i * i <= number; i++) {
        if ((number % i == 0) && (number / i == i)) {
            return true;
        }
    }
    return false;
}
int main() {
    int n = 1024;
    if(isPerfectSquare(n)){
        cout << n << " is perfect square number";
    } else {
        cout << n << " is not a perfect square number";
    }
}

実行結果

1024 is perfect square number

計算量とこの方法のメリット

この手法の時間計算量は O(√n) です。ループは i × i ≤ n が成り立つ間だけ継続するため、反復回数は最大でも √n 回程度に収まります。

sqrt() などの平方根関数を呼び出さないため、浮動小数点演算に伴う丸め誤差の影響を受けることなく、整数演算だけで確実に判定できる点が大きな利点です。特に大きな数値を扱う場合、sqrt の結果を整数にキャストした際の誤差によって誤判定が起こる可能性がありますが、この方法ではその心配がありません。

なお、さらに大きな数値を高速に判定したい場合は、二分探索を利用して O(log n) で求める方法もあります。条件を満たす最小の候補値を絞り込んでいくことで、反復回数を大幅に削減できます。