C++で2と7で割り切れる自然数の合計を求める方法|包除原理による効率的なアルゴリズム

問題概要

本記事では、整数Nが与えられたとき、1からNまでの自然数のうち「2または7で割り切れる数」の合計を求めるアルゴリズムをC++で解説します。

一見すると「2と7の両方で割り切れる数」と誤解されやすいのですが、実際に求めるのは「2で割り切れる、または7で割り切れる」数の総和です。この点を正しく理解することが、適切な解法へたどり着く第一歩となります。

具体例で問題を確認しよう

入力:

N = 10

出力:

37

解説:

1から10までの自然数の中で、2または7で割り切れるのは「2, 4, 6, 7, 8, 10」の6つです。これらをすべて足し合わせると、

sum = 2 + 4 + 6 + 7 + 8 + 10 = 37

となり、答えは37になります。

解法の鍵:包除原理

この問題を解くための基本的なアイデアは包除原理(ほうじょげんり)です。「2で割り切れる数」と「7で割り切れる数」を単純に足し合わせると、14(=2×7)で割り切れる数が二重にカウントされてしまいます。そこで、重複分を引いて補正します。

合計 = (2で割り切れる数の和) + (7で割り切れる数の和) − (14で割り切れる数の和)

等差数列の公式でO(1)計算を実現

各項目の合計は、等差数列(A.P.)の和の公式を利用すれば、ループ処理を一切使わずに定数時間で求められます。

S2  = ((N/2)/2) × (2×2 + (N/2 − 1)×2)
S7  = ((N/7)/2) × (2×7 + (N/7 − 1)×7)
S14 = ((N/14)/2) × (2×14 + (N/14 − 1)×14)

したがって、最終的な合計は次の式で表されます。

Sum = S2 + S7 − S14

この手法により、Nが非常に大きい場合でも瞬時に答えを算出できます。

C++での実装例

上記の考え方を実際にコードにしたものがこちらです。

#include <iostream>
using namespace std;

int findSum(int N) {
    return ( ((N/2)*(2*2+(N/2-1)*2)/2)
           + ((N/7)*(2*7+(N/7-1)*7)/2)
           - ((N/14)*(2*14+(N/14-1)*14)/2) );
}

int main(){
    int N = 42;
    cout<<"2または7で割り切れる自然数の合計は "<<findSum(N);
    return 0;
}

実行結果

2または7で割り切れる自然数の合計は 525

N = 42の場合の計算検証

• 2で割り切れる数(2〜42):21個、合計462
• 7で割り切れる数(7〜42):6個、合計147
• 14で割り切れる数(14〜42):3個、合計84
• 最終的な合計:462 + 147 − 84 = 525

プログラムの出力と一致しており、ロジックが正しく動作していることが確認できます。

まとめ

「2または7で割り切れる自然数の合計」を求める問題は、包除原理と等差数列の和の公式を組み合わせることで、O(1)の計算量で効率的に解くことができます。同様の手法は「3と5で割り切れる数」など、任意の約数の組み合わせにも応用可能です。競技プログラミングやコーディング面接でも頻出のテクニックなので、ぜひマスターしておきましょう。