C++で指定された数より大きい次の完全平方数を求める方法

整数 n が与えられたとき、n より大きい最小の完全平方数（ある整数の 2 乗で表される数）を求める問題を考えてみましょう。例えば、n = 1000 の場合、次の完全平方数は 32² = 1024 となります。

解法の考え方

この問題は、以下のシンプルな手順で解くことができます。

1. 与えられた数 n の平方根を求める
2. その値の小数点以下を切り捨てる（floor 処理）
3. 切り捨てた値に 1 を加え、その 2 乗を計算して返す

n の平方根の整数部分を r とすると、r² ≤ n が成り立つため、n より大きい次の完全平方数は (r + 1)² となります。

C++での実装例

#include<iostream>
#include<cmath>
using namespace std;
int justGreaterPerfectSq(int n) {
    int sq_root = sqrt(n);
    return (sq_root + 1) * (sq_root + 1);
}
int main() {
    int n = 1000;
    cout << "Nearest perfect square: " << justGreaterPerfectSq(n);
}

実行結果

Nearest perfect square: 1024

計算量について

sqrt 関数を 1 回呼び出すだけで処理が完了するため、時間計算量は O(1)、空間計算量も O(1) と非常に効率的です。

注意点

非常に大きな数を扱う場合、浮動小数点演算の誤差により sqrt の結果が不正確になる可能性があります。そのようなケースでは、整数演算による二分探索や、誤差を考慮した補正処理を組み合わせると安全です。