২ থেকে ১০ পর্যন্ত সব দিয়ে বিভাজ্য সংখ্যা গণনা C++-এ

১ থেকে n পর্যন্ত কতটি সংখ্যা ২, ৩, ৪, ৫, ৬, ৭, ৮, ৯, ১০ - সব দিয়ে বিভাজ্য তা বের করতে হবে। এটি সমতুল্য ২৫২০ (LCM of 2..10) দিয়ে বিভাজ্য সংখ্যা গণনা।

উদাহরণ

n = 10000

বিভাজ্য সংখ্যা: 2520, 5040, 7560 → মোট 3টি

অ্যালগরিদম

1. সাধারণ: ১ থেকে n পর্যন্ত লুপে সব সংখ্যা ২-১০ দিয়ে চেক করুন। O(n)
2. দক্ষ (O(1)): ২ থেকে ১০ পর্যন্ত LCM = 2520। ফলাফল = n / 2520

C++ কোড উদাহরণ (দুই পদ্ধতি)

#include <bits/stdc++.h>
using namespace std;

// Naive O(n)
int countDivisibleNaive(int n) {
    int count = 0;
    int divisors[] = {2,3,4,5,6,7,8,9,10};
    for (int i = 1; i <= n; i++) {
        bool ok = true;
        for (int d : divisors)
            if (i % d != 0) { ok = false; break; }
        if (ok) count++;
    }
    return count;
}

// Efficient O(1)
int countDivisibleEfficient(int n) {
    return n / 2520; // LCM(2..10) = 2520
}

int main() {
    int n = 10000;
    cout << "Naive: " << countDivisibleNaive(n) << endl;
    cout << "Efficient: " << countDivisibleEfficient(n);
    return 0;
}

ইনপুট

10000

আউটপুট

3