找出在範圍內不可被任何數整除的數字，使用C++

在本文中，我們將討論查找 1 到 n（給定）之間的數字的問題，這些數字不能被 2 到 10 之間的任何數字整除。讓我們透過一些例子來理解這一點-

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。我們可以根據包含-排除原則來計算。

包含-排除原則

它指出我們應該包括每個單獨集合的大小，你應該刪除成對交集的大小，將三組所有交集的大小相加，依此類推。

找出所有數字的公式是，

= 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 之間不可整除的數字的方法。為了解決這個問題，我們討論了包含排除原則。我們也討論了 C 程序，以應用該方法以 O(1) 複雜度獲得結果。您可以使用任何其他語言（例如 Java、C、Python 等）編寫此程式。我們希望本文對您有所幫助。

以上是找出在範圍內不可被任何數整除的數字，使用C++的詳細內容。更多資訊請關注PHP中文網其他相關文章！