C言語でN以下の「2または5で割り切れる数」の合計を効率的に求める方法

Nまでの自然数のうち、2または5で割り切れる数の合計は、包除原理を用いることで効率的に計算できます。具体的な手順は以下の通りです。

• N以下の自然数の中で2で割り切れる数の合計を求める
• N以下の自然数の中で5で割り切れる数の合計を求める
• 上記2つの合計を足し合わせる
• 最後に、10で割り切れる数（2と5の公倍数）の合計を引く

こうすることで、重複して加算された数が取り除かれ、目的の結果が得られます。この手法は数学的な公式を利用するため、非常に大きなnの値に対しても高速に動作するのが特徴です。

ループを使う方法との比較

ループと条件分岐を使って、2または5で割り切れる数だけを順番に足していく方法を思い浮かべる方もいるかもしれません。しかし、この方法は時間計算量がO(n)（nのオーダー）になるため非効率です。nが大きくなるとループがn回実行され、プログラムの処理負荷が増大してしまいます。

一方、等差数列の和の公式を応用した今回の方法なら、計算量はO(1)で済み、nの値に関わらず一定の速度で結果を求められます。

合計を求める公式

2で割り切れる自然数の合計

Sum2 = ((n / 2) * (4 + (n / 2 - 1) * 2)) / 2

5で割り切れる自然数の合計

Sum5 = ((n / 5) * (10 + (n / 5 - 1) * 5)) / 2

10で割り切れる自然数の合計

Sum10 = ((n / 10) * (20 + (n / 10 - 1) * 10)) / 2

目的の出力（包除原理による最終計算）

Sum = Sum2 + Sum5 - Sum10

C言語での実装例

それでは、実際にC言語でプログラムを書いてみましょう。ここではn=25の場合を例にします。

#include <stdio.h>
int main() {
    int n = 25;
    long int sum2, sum5, sum10;
    sum2 = ((n / 2) * (4 + (n / 2 - 1) * 2)) / 2;
    sum5 = ((n / 5) * (10 + (n / 5 - 1) * 5)) / 2;
    sum10 = ((n / 10) * (20 + (n / 10 - 1) * 10)) / 2;
    long int sum = sum2 + sum5 - sum10;
    printf("Sum is %ld", sum);
    return 0;
}

実行結果

Sum is 201

計算結果の検証

n=25の場合、それぞれの合計は次のようになります。

• Sum2：2+4+6+…+24 = 156
• Sum5：5+10+15+20+25 = 75
• Sum10：10+20 = 30

したがって、156 + 75 − 30 = 201 となり、プログラムの出力と一致します。

まとめ

「2または5で割り切れる数の合計」のような問題では、単純なループ処理ではなく、等差数列の和の公式と包除原理を組み合わせることで、O(1)の定数時間で答えを求められます。競技プログラミングや大規模データの処理などでも役立つテクニックなので、ぜひ覚えておきましょう。