在本文中，我们将讨论查找 1 到 n（给定）之间的数字的问题，这些数字不能被 2 到 10 之间的任何数字整除。让我们通过一些例子来理解这一点 –
Input : num = 14Output : 3Explanation: There are three numbers, 1, 11, and 13, which are not divisible.Input : num = 21Output : 5Explanation: 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 整除。
立即学习“C++免费学习笔记（深入）”；
我们需要找到所有能被 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 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++的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445123.html
微信扫一扫 
支付宝扫一扫 
