最初のn個の自然数の二乗和を求めるC++プログラムの解説

はじめに

この記事では、最初のn個の自然数（1からnまで）の二乗和を求める方法について解説します。例えば、n = 4 の場合、計算結果は 1² + 2² + 3² + 4² = 1 + 4 + 9 + 16 = 30 となります。

基本的なアプローチとしては、1からnまで繰り返すforループを使用し、各ステップで項の二乗を計算して合計に加算していく方法があります。このプログラムの計算量は O(n) です。

しかし、O(1) の定数時間で解きたい場合は、次の級数の公式を利用できます。

Σk² = n(n + 1)(2n + 1) / 6

この公式を使えば、ループ処理を行わずに一発で答えを求めることが可能です。

アルゴリズム

squareNNatural(n)

begin
    sum := 0
    for i in range 1 to n, do
        sum := sum + i^2
    done
    return sum
end

サンプルコード（C++）

以下は、forループを使用して二乗和を計算するC++プログラムの実装例です。

#include<iostream>
using namespace std;
long square_sum_n_natural(int n) {
    long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i * i; // iの二乗を計算してsumに加算
    }
    return sum;
}
main() {
    int n;
    cout << "Enter N: ";
    cin >> n;
    cout << "Result is: " << square_sum_n_natural(n);
}

実行結果

Enter N: 4
Result is: 30

補足：O(1)で高速化する方法

上記のプログラムは分かりやすい反面、nが大きくなると処理時間が線形に増加します。先述の公式 n(n + 1)(2n + 1) / 6 を使えば、以下のようにループなしで即座に結果を得られます。

long square_sum_n_natural_fast(int n) {
    return (long)n * (n + 1) * (2 * n + 1) / 6;
}

大きなnを扱う場合やパフォーマンスが重視される場面では、公式によるO(1)の実装を選択するのが効果的です。なお、nが大きい場合にはオーバーフローに注意し、必要に応じてより大きな整数型を使用してください。