使用 C++ 找出不能被 [2, 10] 范围内的任何数字整除的数字

在本文中，我们将讨论从1到n(given)不能被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; //应用包含-排除原则的公式 //找出不能被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 << "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等）编写此程序。我们希望本文对您有所帮助。