ในปัญหานี้ เราได้รับตัวเลข N หน้าที่ของเราคือค้นหาทวีคูณของ 2 หรือ 3 หรือ 5 น้อยกว่าหรือเท่ากับ N
คำอธิบายปัญหา − เราจะนับองค์ประกอบทั้งหมดตั้งแต่ 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), count++.
ขั้นตอนที่ 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<<"The number of multiples till "<<n<<" is "<<countMultiples(n)<<endl;
return 0;
} ผลลัพธ์
The number of multiples till 13 is 9
