資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告