数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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 整除的数字。
算法
初始化 − count = 0
步骤 1 − 循环 i 从 1 到 N。
步骤 1.1: 如果 (i%2 == 0 || i%3 == 0 || i%5 == 0)，则 count++。
步骤 2 − 返回 count。
另一种方法
解决这个问题的一个更有效的方法是使用集合论。
能被 2 整除的数字个数为 n(2)
能被 3 整除的数字个数为 n(3)
能被 5 整除的数字个数为 n(5)
能被 2 和 3 整除的数字个数为 n(2 ∩ 3)
能被 2 和 5 整除的数字个数为 n(2 ∩ 5)
能被 3 和 5 整除的数字个数为 n(3 ∩ 5)
能被 2 和 3 和 5 整除的数字个数为 n(2 ∩ 3 ∩ 5)
能被 2 或 3 或 5 整除的数字个数为 n(2 ∪ 3 ∪ 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<<"The number of multiples till "<<n<<" is "<<countMultiples(n)<<endl;
return 0;
}输出
The number of multiples till 13 is 9
更新于: 2021年3月12日
275 次浏览
广告