C++ を使用して、範囲内のどの数値でも割り切れない数値を検索します。

この記事では、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 などの他の言語で作成できます。この記事がお役に立てば幸いです。

以上がC++ を使用して、範囲内のどの数値でも割り切れない数値を検索します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。