好资源导航 » 文章资讯 » 在C ++中查找小于或等于N的2或3或5的倍数

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

2024-02-21 17:16:03 58

在此问题中，给我们一个数字N。我们的任务是查找小于或等于N的2或3或5的倍数。

问题描述-我们将计算从1到N的所有可被2或3或5整除的元素。

让我们举个例子来了解这个问题，

输入

N = 7

输出结果

解释

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（2n3）

被2和5整除的数字的计数为n（2n5）

被3和5整除的数的计数为n（3n5）

被2、3和5整除的数字的计数为n（2n3n5）

可被2或3或5整除的数的计数为n（2U3U5）

根据集合论，

n（2∪3∪5）=n(2)+n(3)+n(5)-n（2∩3）-n（2∩5）-n（3∩5）+n（2∩3∩5）

通过计算数字的位掩码可以找到解决方案。

该程序说明了我们解决方案的工作原理，

示例

#include 
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<<"直到的倍数 "<输出结果直到的倍数 13 is 9

返回顶部
514930285
czq8825@qq.com

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

输入

解释

解决方法

算法

另一种方法

示例

热门推荐

随机推荐