এই সমস্যায়, আমাদের একটি সংখ্যা দেওয়া হয়েছে। আমাদের কাজ হল 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 দ্বারা ভাগ করা সমস্ত সংখ্যা গণনা করা৷
অ্যালগোরিদম
শুরু করুন - গণনা =0
ধাপ 1 i =1 থেকে N.
এর জন্য লুপপদক্ষেপ 1.1৷ :যদি(i%2 ==0 || i%3 ==0 || i%5 ==0), গণনা++।
ধাপ 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
