C++-এ দেওয়া রেঞ্জে বিজোড় সংখ্যক ডিভাইজার থাকা সংখ্যা গণনা করার প্রোগ্রাম

সমস্যা বিবরণ

একটি রেঞ্জ [a, b] দেওয়া থাকলে, কতগুলো সংখ্যার ডিভাইজার সংখ্যা বিজোড় (odd) তা বের করুন।

গাণিতিক অন্তর্দৃষ্টি: একটি সংখ্যার ডিভাইজার সংখ্যা বিজোড় হলে সেটি পূর্ণবর্গ (perfect square) হতে হবে। কারণ ডিভাইজার জোড়ায় আসে, শুধু বর্গমূল অযুগ্ম থাকে।

সমাধানের পদ্ধতি

1. রেঞ্জ [a, b]-এ কতগুলো পূর্ণবর্গ আছে তা বের করুন।
2. উত্তর = floor(sqrt(b)) - ceil(sqrt(a)) + 1।
3. ব্রুট-ফোর্স (দেওয়া কোড): প্রতিটি সংখ্যার ডিভাইজার কাউন্ট করুন।

C++ কোড উদাহরণ (ব্রুট-ফোর্স)

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

int OddDivCount(int a, int b) {
    int res = 0;
    for (int i = a; i <= b; ++i) {
        int divCount = 0;
        for (int j = 1; j <= i; ++j) {
            if (i % j == 0) ++divCount;
        }
        if (divCount % 2) ++res;
    }
    return res;
}

// অপ্টিমাইজড ভার্সন:
int OddDivCountOptimized(int a, int b) {
    int start = ceil(sqrt(a));
    int end = floor(sqrt(b));
    return max(0, end - start + 1);
}

int main() {
    int a = 1, b = 10;
    cout << OddDivCount(a, b) << endl;
    cout << "Optimized: " << OddDivCountOptimized(a, b) << endl;
    return 0;
}

আউটপুট

3

ব্যাখ্যা

রেঞ্জ ১ থেকে ১০: পূর্ণবর্গ = 1, 4, 9 → ৩টি

জটিলতা

• ব্রুট-ফোর্স: O(n√n)
• অপ্টিমাইজড: O(1)