Trong bài toán này, chúng ta được cho một số N. Nhiệm vụ của chúng ta là Tìm bội số của 2 hoặc 3 hoặc 5 nhỏ hơn hoặc bằng N.
Mô tả sự cố - Chúng tôi sẽ đếm tất cả các phần tử từ 1 đến N chia hết cho 2 hoặc 3 hoặc 5.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 7
Đầu ra
5
Giải thích
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
Phương pháp tiếp cận giải pháp
Một cách tiếp cận đơn giản để giải quyết vấn đề là duyệt qua tất cả các số từ 1 đến N và đếm tất cả các số chia hết cho 2 hoặc 3 hoặc 5.
THUẬT TOÁN
Khởi tạo - count =0
Bước 1 - vòng lặp cho i =1 đến N.
Bước 1.1 :if (i% 2 ==0 || i% 3 ==0 || i% 5 ==0), count ++.
Bước 2 - số lần trả lại.
Một cách tiếp cận khác
Một cách tiếp cận hiệu quả hơn để giải quyết vấn đề là sử dụng lý thuyết tập hợp.
Tổng số số chia hết cho 2 là n (2)
Tổng số số chia hết cho 3 là n (3)
Số lượng chia hết cho 5 là n (5)
Số lượng số chia hết cho 2 và 3 là n (2 n 3)
Số đếm chia hết cho 2 và 5 là n (2 n 5)
Số đếm chia hết cho 3 và 5 là n (3 n 5)
Số đếm chia hết cho 2 và 3 và 5 là n (2 n 3 n 5)
Số đếm chia hết cho 2 hoặc 3 hoặc 5 là n (2 Ư 3 Ư 5)
Dựa trên lý thuyết tập hợp,
n (2 ∪ 3 ∪ 5) =n (2) + n (3) + n (5) - n (2 ∩ 3) - n (2 ∩ 5) - n (3 ∩ 5) + n (2 ∩ 3 ∩ 5)
Giải pháp được tìm thấy bằng cách tính toán mặt nạ bit của các số.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The number of multiples till 13 is 9