Cプログラムで最初のn個の自然数の総和の合計を求める方法

自然数の総和の合計とは

「自然数の総和の合計」とは、まず1からnまでの各整数についてそこまでの累積和を求め、その後、得られたすべての和を足し合わせて最終的な値を求めるという考え方です。

この問題では、合計を求める上限となる数nが与えられます。具体例を使って確認してみましょう。

n = 4

1から4までの各数値ごとに、そこまでの累積和を計算します。

1までの和 = 1
2までの和 = 1 + 2 = 3
3までの和 = 1 + 2 + 3 = 6
4までの和 = 1 + 2 + 3 + 4 = 10

次に、これらの累積和をすべて足し合わせます。

合計 = 1 + 3 + 6 + 10 = 20

このように、n = 4 のときの答えは 20 になります。

最初のn個の自然数の総和の合計を求めるには、大きく分けて2つの方法があります。

• 方法1：forループを使用する（非効率）
• 方法2：数学公式を使用する（効率的）

方法1：forループを使う方法

この方法では、2重のforループを使って総和の合計を求めます。内側のループが1からiまでの自然数の和を計算し、外側のループがその和を合計sumに加算しながらiを1ずつ増やしていきます。なお、各反復の前に累積和用の変数sを必ずリセットしてください。リセットを忘れると正しい結果が得られません。

サンプルコード

#include <stdio.h>

int main() {
    int n = 4;
    int sum = 0, s = 0;

    for (int i = 1; i <= n; i++) {
        s = 0; /* 累積和を初期化 */
        for (int j = 1; j <= i; j++) {
            s += j;
        }
        sum += s;
    }

    printf("1から%dまでの自然数の総和の合計は %d です\n", n, sum);
    return 0;
}

実行結果

1から4までの自然数の総和の合計は 20 です

この方法はロジックが直感的で理解しやすい反面、2重ループ構造のため計算量がO(n²)となり、nが大きくなるほど処理時間が長くなります。

方法2：数学公式を使う方法

最初のn個の自然数の総和の合計を求めるための数学公式が知られています。公式を使えばループ処理が不要になり、計算量はO(1)で済むため、非常に効率的な方法です。

使用する公式は次のとおりです。

sum = n × (n + 1) × (n + 2) / 6

この式が表すのは「四面体数」と呼ばれる数列で、三角数（1, 3, 6, 10, …）の累積和に相当します。n = 4 の場合、4 × 5 × 6 ÷ 6 = 20 となり、ループによる結果と一致します。

サンプルコード

#include <stdio.h>

int main() {
    int n = 4;
    int sum = (n * (n + 1) * (n + 2)) / 6;

    printf("1から%dまでの自然数の総和の合計は %d です\n", n, sum);
    return 0;
}

実行結果

1から4までの自然数の総和の合計は 20 です

まとめ

• forループ版：計算量はO(n²)。仕組みの理解に適していますが、大きなnには不向きです。
• 数学公式版：計算量はO(1)。n(n+1)(n+2)/6 を使えば即座に答えが求まり、実務でも推奨されます。

パフォーマンスを重視する場合は、数学公式を使った方法2を選択するのがベストです。