C ++を使用して、[2、10]の範囲の数値で割り切れない数値を見つけます

この記事では、2から10までのどの数でも割ることができない1からn（与えられた）までの数を見つける問題について説明します。いくつかの例でこれを理解しましょう-

Input : num = 14
Output : 3
Explanation: There are three numbers, 1, 11, and 13, which are not divisible.

Input : num = 21
Output : 5
Explanation: There are five numbers 1, 11, 13, 17, and 19, which are not divisible.

解決策を見つけるためのアプローチ

シンプルなアプローチ

1からnumまでのすべての数値をチェックする場合、2から10までの任意の数値で除算できるかどうかを確認します。そうでない場合は、カウントを増やします。ただし、このアプローチには時間がかかりすぎるため、時間の複雑さが増します。

効率的なアプローチ

私たちが考えることができる最善のアプローチは、最初に1からnumまでの数値を見つけ、[2、10]の範囲内の任意の数値で割り切れ、次にこのカウントをnumで引くことです。

したがって、最初に、2、3、4、5、10で割り切れるすべての数値を見つける必要があります。ただし、4、6、8、および10で割り切れる数は2で割り切れ、3で割り切れる数は6と9で割り切れます。

2、3、5、および7で割り切れるすべての数値を見つける必要があります。これは、包除原理から計算できます。

包除原理

すべての単一セットのサイズを含める必要がある、ペアワイズ交差のサイズを削除する必要がある、3セットのすべての交差のサイズを追加する必要がある、などと記載されています。

すべての数値を見つける式は、

= NUM – X + Y – Z + A.

どこで、

X = num divisible by 2, 3, 5, 7 ( [num / 2] + [num / 3] + [num / 5] + [num / 7] )

Y = num divisible by (2,3), (2, 5), (2, 7), (3, 5), (3, 5), (3, 7) and (5, 7) = ( [num / (2 * 3)] + [num / (2 * 5)] + [num / (2 * 7)] + [num / (3 * 5)] + num / (3 * 7)] + [num / (5 * 7)] ).

Z = num divisible by (2, 3, 5), (2, 3, 7), (2, 5, 7) and (3, 5, 7) = ( [num / (2 * 3 * 5)] + [num / (2 * 3 * 7)] + [num / (2 * 5 * 7)] + [num / (3 * 5 * 7)] )

A = num divisible by (2, 3, 5, 7) = ( [num / (2 * 3 * 5 * 7)] )

例

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

int main() {
   int n = 21, result;
   // applying formula from inclusion - exclusion principle
   // to find the count of numbers not divisible by any number from 2 to 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 << "The count of numbers, not div by [2, 10] is: " << result;

   return 0;
}

出力

The count of numbers, not div by [2, 10] is: 5

結論

この記事では、2からnまでの除算できない数を見つける方法について説明しました。この問題を解決するために、包除原理について説明しました。また、O（1）の複雑さで結果を取得するためのアプローチを適用するC++プログラムについても説明しました。このプログラムは、Java、C、Pythonなどの他の言語で作成できます。この記事がお役に立てば幸いです。