使用 C++ 查找不能被 [2, 10] 范围内的任何数字整除的数字
c++server side programmingprogramming
在本文中，我们将讨论从 1 到 n(给定)的数字的问题，这些数字不能被 2 到 10 之间的任何数字整除。让我们通过一些示例来理解这一点 −
输入:num = 14 输出:3 说明:有三个数字，1、11 和 13，它们不能被整除。 输入:num = 21 输出:5 说明:有五个数字 1、11、13、17 和 19，它们不能被整除。
寻找解决方案的方法
简单方法
如果我们检查从 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 << "未被 [2, 10] 整除的数字数量为:<< result;
return 0;
}
输出
未被 [2, 10] 整除的数字数量为:5
结论
在本文中，我们讨论了从 2 到 n 查找不可整除数字的方法。为了解决这个问题，我们讨论了包含-排除原则。我们还讨论了应用该方法以 O(1) 复杂度获得结果的 C++ 程序。您可以使用任何其他语言(如 Java、C、Python 等)编写此程序。我们希望您觉得这篇文章有用。
