C++でN以下の2・3・5の倍数を数える方法｜包除原理による効率的なアルゴリズム

この問題では、整数 N が与えられ、N 以下にある 2・3・5 のいずれかの倍数をすべて求めることが課題になります。

問題の概要

1 から N までの整数のうち、2・3・5 の少なくとも 1 つで割り切れる数が全部でいくつあるかを数えます。

入力例

N = 7

出力例

5

解説

1 から 7 までの要素：1, 2, 3, 4, 5, 6, 7
2・3・5 のいずれかで割り切れる要素：2, 3, 4, 5, 6

解法① 全探索（シンプルなアプローチ）

最も基本的な解法は、1 から N まですべての数を順番にチェックし、2・3・5 のいずれかで割り切れる数をカウントしていく方法です。

アルゴリズム

初期化 − count = 0

ステップ 1 − i = 1 から N までループする。

ステップ 1.1 − i % 2 == 0 || i % 3 == 0 || i % 5 == 0 を満たす場合、count を 1 増やす。

ステップ 2 − count を返す。

この方法の計算量は O(N) となり、N が大きくなるほど処理に時間がかかるという弱点があります。

解法② 包除原理（集合論）を使った効率的なアプローチ

より効率よく解くには、集合論の包除原理（inclusion-exclusion principle）を活用します。まず、次のように記号を定義しましょう。

• 2 の倍数の個数：n(2)
• 3 の倍数の個数：n(3)
• 5 の倍数の個数：n(5)
• 2 と 3 の公倍数の個数：n(2 ∩ 3)
• 2 と 5 の公倍数の個数：n(2 ∩ 5)
• 3 と 5 の公倍数の個数：n(3 ∩ 5)
• 2・3・5 の公倍数の個数：n(2 ∩ 3 ∩ 5)
• 2・3・5 のいずれかの倍数の個数：n(2 ∪ 3 ∪ 5)

包除原理によれば、これらの間には次の関係が成り立ちます。

n(2 ∪ 3 ∪ 5) = n(2) + n(3) + n(5) − n(2 ∩ 3) − n(2 ∩ 5) − n(3 ∩ 5) + n(2 ∩ 3 ∩ 5)

ここで、k の倍数の個数は n(k) = ⌊N / k⌋ として即座に求められるため、各項は定数時間で計算できます。「足しすぎた分を引き、引きすぎた分を足す」という操作を重複分に対して行うことで、正確な個数が得られます。

ビットマスクによる実装の考え方

{2, 3, 5} という 3 つの数の選び方は 2³ = 8 通りあり、それぞれをビットマスク（000 〜 111）に対応させます。各ビットマスクについて選ばれた数の積を計算し、選んだ個数が奇数なら加算・偶数なら減算を行えば、包除原理の計算を自動的に実現できます。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;

int countMultiples(int n) {
    int values[] = { 2, 3, 5 };
    int countMultiples = 0, bitMask = pow(2, 3);
    for (int i = 1; i < bitMask; i++) {
        int prod = 1;
        for (int j = 0; j < 3; j++) {
            if (i & (1 << j))
                prod = prod * values[j];
        }
        if (__builtin_popcount(i) % 2 == 1)
            countMultiples = countMultiples + n / prod;
        else
            countMultiples = countMultiples - n / prod;
    }
    return countMultiples;
}

int main() {
    int n = 13;
    cout << "The number of multiples till " << n << " is " << countMultiples(n) << endl;
    return 0;
}

実行結果

The number of multiples till 13 is 9

N = 13 の場合、2 の倍数は 6 個、3 の倍数は 4 個、5 の倍数は 2 個あり、公倍数による重複を包除原理で除去すると合計 9 個となり、プログラムが正しく動作していることが確認できます。

まとめ

N が小さい場合は全探索でも十分ですが、N が大きいケースでは包除原理を使うことで、ループ回数が固定の 2³ = 8 回で済み、実質 O(1) で答えを求められます。一般に k 個の数の倍数を数える場合の計算量は O(2^k) となるため、対象の数が少ない問題で特に威力を発揮するテクニックです。