在此问题中,给我们一个数字N。我们的任务是查找小于或等于N的2或3或5的倍数。
问题描述-我们将计算从1到N的所有可被2或3或5整除的元素。
让我们举个例子来了解这个问题,
N = 7输出结果
5
All the elements from 1 to 7 are : 1, 2, 3, 4, 5, 6, 7. Elements divisible by 2/3/5 are 2, 3, 4, 5, 6
解决此问题的一种简单方法是遍历从1到N的所有数字,并计算除以2或3或5的所有数字。
初始化-计数= 0
步骤1-循环i = 1到N。
步骤1.1:if(i%2 == 0 || i%3 == 0 || i%5 == 0),计数++。
步骤2-返回计数。
解决问题的一种更有效的方法是使用集合理论。
被2整除的数的计数为n(2)
可被3整除的数为n(3)
被5整除的数为n(5)
被2和3整除的数的计数为n(2 n 3)
被2和5整除的数字的计数为n(2 n 5)
被3和5整除的数的计数为n(3 n 5)
被2、3和5整除的数字的计数为n(2 n 3 n 5)
可被2或3或5整除的数的计数为n(2 U 3 U 5)
根据集合论,
n(2∪3∪5)= n(2)+ n(3)+ n(5)-n(2∩3)-n(2∩5)-n(3∩5)+ n(2∩3 ∩5)
通过计算数字的位掩码可以找到解决方案。
该程序说明了我们解决方案的工作原理,
#include <bits/stdc++.h> using namespace std; int countMultiples(int n) { int values[] = { 2, 3, 5 }; int countMultiples = 0, bitMask = pow(2, 3); for (int i = 1; i < bitMask; i++) { int prod = 1; for (int j = 0; j < 3; j++) { if (i & 1 << j) prod = prod * values[j]; } if (__builtin_popcount(i) % 2 == 1) countMultiples = countMultiples + n / prod; else countMultiples = countMultiples - n / prod; } return countMultiples; } int main() { int n = 13; cout<<"直到的倍数 "<<n<<" is "<<countMultiples(n)<<endl; return 0; }输出结果
直到的倍数 13 is 9