完全平方数（パーフェクトスクエア）かどうかを判定するアルゴリズムとC++実装

ある数の平方根が整数になるとき、その数は完全平方数（パーフェクトスクエア）と呼ばれます。つまり、平方根が整数値になるような数が完全平方数です。例えば、4 の平方根は 2、25 の平方根は 5 であるため、どちらも完全平方数です。

完全平方数を判定する最も基本的な方法は、対象の数の平方根を求め、それが整数に一致するかどうかを繰り返し確認することです。計算した二乗の値が対象の数を超えた時点で一致しなければ、その数は完全平方数ではありません。

ただし、この記事では処理を効率化するため、平方根を何度も再計算する方式は採用していません。完全平方数の平方根は必ず整数になるという性質を利用し、候補となる平方根を 1 ずつ増やしながら、その二乗が対象の数と一致するかどうかを順番にチェックします。これにより、無駄な計算を省き、シンプルかつ確実な判定が可能になります。

入力と出力

入力:
判定する数: 1032

出力:
1032 は完全平方数ではありません。

アルゴリズム

判定関数 isPerfectSquare(num) の流れは以下の通りです。

入力: 判定対象の数。

出力: 対象の数が完全平方数であれば true（平方根の値も返す）。そうでなければエラーを返す。

Begin
    if num < 0, then
        exit
    sqRoot := 1
    sq := sqRoot^2
    while sq <= num, do
        if sq = num, then
            return sqRoot
        sqRoot := sqRoot + 1
        sq := sqRoot^2
    done
    otherwise return error
End

アルゴリズムのポイント

• 負の数は平方根を持たないため、最初に除外します。
• 候補の平方根 sqRoot を 1 から開始し、その二乗が対象の数以下である間ループを続けます。
• 二乗した値が対象の数と一致すれば、その時点の sqRoot が答えとなります。
• 二乗した値が対象の数を超えたら、完全平方数ではないと判断できます。

C++による実装例

#include<iostream>
using namespace std;

int isPerfectSquare(int num) {
    if(num < 0)
        return -1;          // 負の数は有効な平方数ではない
    int sqRoot = 1, sq;

    while((sq =(sqRoot*sqRoot)) <= num) {   // 二乗値が対象の数を超えていない間繰り返す
        if(sq == num)
            return sqRoot;
        sqRoot++;           // 完全平方数の平方根は必ず整数なので1ずつ増やす
    }
    return -1;
}

int main() {
    int num, res;
    cout << "Enter a number to check whether it is perfect square or not: ";
    cin >> num;

    if((res = isPerfectSquare(num)) != -1)
        cout << num << " is a perfect square number, square root: " << res;
    else
        cout << num << " is not a perfect square number.";
}

実行結果

Enter a number to check whether it is perfect square or not: 1032
1032 is not a perfect square number.

このプログラムでは、1032 を入力すると、1²=1、2²=4、…と順に確認していきますが、32²=1024、33²=1089 となり、1032 に一致する整数の二乗は存在しないため、「完全平方数ではない」という結果が出力されます。逆に、例えば 1024 を入力すれば、平方根 32 が返され、完全平方数であると判定されます。