C++で2から10までのすべての数で割り切れる数を数える方法

問題概要

ある整数 num が与えられたとき、1からnumまでの範囲に含まれる数のうち、2、3、4、5、6、7、8、9、10のすべてで割り切れる数がいくつあるかを求めるのが課題です。

入力: int num = 10000

出力: 2から10までのすべての数で割り切れる数の個数： 3

説明: 1から10000までの範囲には、2から10までのすべての数で割り切れる数が3つ存在します。具体的には 2520、5040、7560 の3つです。

入力: int num = 20000

出力: 2から10までのすべての数で割り切れる数の個数： 7

説明: 1から20000までの範囲では、該当する数は7つになります。具体的には 2520、5040、7560、10080、12600、15120、17640 です。

プログラムで使用するアプローチ

この問題を解くには、素朴な方法（ナイーブな手法）と効率的な手法など、複数のアプローチがあります。まずはナイーブな手法から見ていきましょう。

• 数値numを入力として受け取る
• 2から10までの数を、長さ9の固定長int型配列に格納する
• 一時変数として、該当数の合計を保持するcountと、割り切れるかどうかを判定するためのflagを用意する
• iを1からnumまでforループで繰り返す
• ループ内で、numにiを設定し、indexを0に初期化する
• indexが9（配列のサイズ）未満である間、whileループを回す
• num % arr[index++] == 0 であればflagを1に、そうでなければflagを0にしてbreakする
• flagが1であればcountを1増やす
• countを返す
• 結果を出力する

効率的なアプローチ

2から10までのすべての数で割り切れる数には、明確なパターンがあります。

2から10までのすべての数で割り切れる最小の数は2520です。これは2〜10の最小公倍数（LCM）に相当します。

5 * 7 * 8 * 9 = 2520（n = 1）
5 * 7 * 8 * 9 * 2 = 5040（n = 2）
5 * 7 * 8 * 9 * 3 = 7560（n = 3）
.
.

このように、2、3、4、5、6、7、8、9、10のすべてで割り切れる数は、必ず2520を公約数として持ちます。したがって、与えられた数を2520で割るだけで答えが求まります。

コード1（ナイーブな手法）

例

#include <bits/stdc++.h>
using namespace std;
int count(int num){
    int count = 0;
    int flag = 0;
    int index = 0;
    int arr[9] = {2, 3, 4, 5, 6, 7, 8, 9, 10};
    for (int i = 1; i <= num; i++){
        int num = i;
        index = 0;
        while(index < 9){
            if(num % arr[index++] == 0){
                flag = 1;
            }
            else{
                flag = 0;
                break;
            }
        }
        if (flag == 1){
            count++;
        }
    }
    return count;
}
int main(){
    int num = 10000;
    cout<<"2から10までのすべての数で割り切れる数の個数： "<<count(num);
return 0;
}

出力

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

2から10までのすべての数で割り切れる数の個数： 3

コード2（効率的な手法）

例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int num = 10000;
    int count = num / 2520;
    cout<<"2から10までのすべての数で割り切れる数の個数： "<<count;
    return 0;
}

出力

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

2から10までのすべての数で割り切れる数の個数： 3

まとめ

ナイーブな手法の計算量は O(num × 9) となり、numが大きくなるほど処理時間が大幅に増加します。一方、効率的な手法は除算を1回行うだけでよいため、O(1)の計算量で結果を得られます。問題の背後にある数学的パターン（ここでは最小公倍数2520）を見抜くことで、処理を劇的に高速化できる好例といえるでしょう。