C++で%演算子を使わずに3と5の倍数を判定する方法

通常、ある数が3や5の倍数であるかどうかを調べるには、% 演算子(剰余演算子)を使えば簡単に実装できます。しかし、この問題では % 演算子を使用することが禁止されています。

そこで本記事では、+ 演算子(加算)を活用するアプローチを紹介します。考え方はシンプルで、「前の倍数に3または5を足せば次の倍数になる」という性質を利用します。まずは具体例を見てみましょう。

入力例と出力例

入力

15

出力

1
2
3 - Multiple of 3
4
5 - Multiple of 5
6 - Multiple of 3
7
8
9 - Multiple of 3
10 - Multiple of 5
11
12 - Multiple of 3
13
14
15 - Multiple of both 3 and 5

アルゴリズム

• 判定対象となる数 n を初期化します。
• 次に現れる 3 の倍数と 5 の倍数を追跡するための変数を2つ用意します。
• 初期値はそれぞれ 3 と 5 とします。
• 1 から n まで(両端を含む)を繰り返すループを作成します。
  • 追跡用変数と現在の数を比較し、その数が3の倍数かどうかを判定します。
  • 同様に、5の倍数かどうかも判定します。
  • もし3の倍数なら、追跡変数に3を加算して次の倍数を更新します。5の倍数の場合も同様に5を加算します。
  • 判定結果に応じて、対応するテキストをコンソールに出力します。

C++での実装

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

#include <bits/stdc++.h>
using namespace std;
void findMultiplesOf3And5(int n) {
    int threeMultiple = 3;
    int fiveMultiple = 5;
    for (int i = 1; i <= n; i++) {
        bool _3 = false, _5 = false;
        if (i == threeMultiple) {
            threeMultiple += 3;
            _3 = true;
        }
        if (i == fiveMultiple) {
            fiveMultiple += 5;
            _5 = true;
        }
        if (_3 && _5) {
            cout << "Multiple of both 3 and 5" << endl;
        }else if (_3) {
            cout << "Multiple of 3" << endl;
        }else if (_5) {
            cout << "Multiple of 5" << endl;
        }else {
            cout << i << endl;
        }
    }
}
int main() {
    findMultiplesOf3And5(100);
    return 0;
}

実行結果

上記のコードを実行すると、次のような結果が得られます(n=100の場合)。ここでは冒頭部分のみを抜粋して示します。以降も同じパターンが100まで続きます。

1
2
Multiple of 3
4
Multiple of 5
Multiple of 3
7
8
Multiple of 3
Multiple of 5
11
Multiple of 3
13
14
Multiple of both 3 and 5
16
17
Multiple of 3
19
Multiple of 5
...

ポイントのまとめ

この手法のポイントは、剰余計算を行わずに「次の倍数」を事前に記憶しておくことです。3の倍数は3ずつ、5の倍数は5ずつ増えていくため、加算だけで倍数判定が完結します。計算量はO(n)、追加のメモリは定数個の変数のみで済むため、非常に効率的な方法といえます。なお、15のように3と5の両方の倍数(つまり15の倍数)になる場合は、「Multiple of both 3 and 5」として両方の条件を満たすことを明示しています。