【C++】1〜nの中で2〜10のどの数でも割り切れない数を効率的に求める方法

本記事では、1からn（入力値）までの数のうち、2から10までのどの数でも割り切れない数を求める問題について解説します。まずは具体例でイメージをつかみましょう。

入力 : num = 14
出力 : 3
説明 : 割り切れない数は 1、11、13 の3つです。

入力 : num = 21
出力 : 5
説明 : 割り切れない数は 1、11、13、17、19 の5つです。

解決策へのアプローチ

単純な方法

最も素直な方法は、1からnumまでの各数値について、2から10までのいずれかの数で割り切れるかを順番にチェックしていくことです。割り切れない場合はカウントを増やします。しかし、この方法は1つひとつの数を確認するため処理時間が長くなり、計算量が大きくなってしまうという欠点があります。

効率的な方法

より優れたアプローチは、「1からnumまでの数のうち、2〜10の範囲内のいずれかの数で割り切れる数の個数」を先に求め、それをnumから引くというものです。

ここで重要なのは、4、6、8、10で割り切れる数はすべて2で割り切れ、6と9で割り切れる数はすべて3で割り切れるという点です。つまり、結局調べるべきは2、3、5、7で割り切れる数だけでよいことになります。この個数の計算には「包除原理」が活用できます。

包除原理とは

包除原理とは、複数の集合の合計サイズを正しく求めるための定理です。具体的には、各集合のサイズを加算し、2つの集合の共通部分（重なり）のサイズを差し引き、さらに3つの集合の共通部分のサイズを加算し……という操作を繰り返します。

この問題において、2〜10のいずれかで割り切れる数の総数を求める式は次のようになります。

= NUM − X + Y − Z + A

各項の意味は以下の通りです。

X = 2、3、5、7 のいずれかで割り切れる数
    （ [num / 2] + [num / 3] + [num / 5] + [num / 7] ）

Y = 2つの数の積（6、10、14、15、21、35）で割り切れる数
    （ [num / 6] + [num / 10] + [num / 14] + [num / 15] + [num / 21] + [num / 35] ）

Z = 3つの数の積（30、42、70、105）で割り切れる数
    （ [num / 30] + [num / 42] + [num / 70] + [num / 105] ）

A = 4つの数の積（210）で割り切れる数
    （ [num / 210] ）

C++による実装例

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

int main() {
    int n = 21, result;
    // 包除原理の公式を適用し、
    // 2〜10のどの数でも割り切れない数の個数を求める
    result = n - n / 2 - n / 3 - n / 5 - n / 7
         + n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35
         - n / 30 - n / 42 - n / 70 - n / 105 + n / 210;
    cout << "2〜10で割り切れない数の個数は: " << result;

    return 0;
}

出力結果

2〜10で割り切れない数の個数は: 5

まとめ

本記事では、1からnまでの数のうち2〜10のいずれでも割り切れない数を求める方法を解説しました。この問題は包除原理を用いることで、ループによる全件チェックを行わずともO(1)の計算量で答えを導き出せます。紹介したプログラムはC++で記述していますが、同じ考え方はJava、C、Pythonなど他の言語にもそのまま応用できます。ぜひ実際にコードを書いて試してみてください。