在C ++中查找小于或等于N的2或3或5的倍数

在此问题中,给我们一个数字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