C++で3または7の倍数の個数を求める方法

数値 n が与えられたとき、n までに含まれる 3 または 7 の倍数の個数を求める問題を考えます。まずは具体例を見てみましょう。

入出力の例

入力

100

出力

43

100 までには、3 または 7 の倍数が合計 43 個存在します。

アルゴリズム

• 数値 n を初期化します。

• カウント用の変数を 0 で初期化します。

• 3 から n まで繰り返すループを作成します。

  • 現在の数値が 3 または 7 で割り切れる場合は、カウントを 1 増やします。

C++での実装

以下は、上記のアルゴリズムを C++ で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
int getMultiplesCount(int n) {
    int count = 0;
    for (int i = 3; i <= n; i++) {
        if (i % 3 == 0 || i % 7 == 0) {
            count++;
        }
    }
    return count;
}
int main() {
    cout << getMultiplesCount(100) << endl;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

43

補足：包除原理による高速化

ループを使わずに、包除原理を利用すれば答えを直接計算することもできます。n までの 3 の倍数は ⌊n/3⌋ 個、7 の倍数は ⌊n/7⌋ 個あり、両方に重複して含まれる 21 の倍数は ⌊n/21⌋ 個です。したがって、答えは次の式で求められます。

⌊n/3⌋ + ⌊n/7⌋ − ⌊n/21⌋

n = 100 の場合、33 + 14 − 4 = 43 となり、先ほどの実行結果と一致します。この方法なら O(1) の時間で計算できるため、n が非常に大きい場合にも効率的に対応できます。