C++-এ [1, N] রেঞ্জে অনন্য প্রাইম ফ্যাক্টরের সর্বোচ্চ সংখ্যা

দেওয়া কাজ হল [1, N] রেঞ্জে একটি সংখ্যা যেটি সর্বোচ্চ কতগুলো অনন্য প্রাইম ফ্যাক্টর ধারণ করতে পারে তা খুঁজে বের করা, যেখানে N দেওয়া আছে।

উদাহরণ দিয়ে বোঝা যাক

ইনপুট - N=100

আউটপুট - ৩

ব্যাখ্যা - [1, 100] রেঞ্জে ৩০ নিই। ৩০ = ৩ * ২ * ৫ = অনন্য প্রাইম ফ্যাক্টর। তাই [1, 100] রেঞ্জে সর্বোচ্চ ৩টি অনন্য ফ্যাক্টর পাওয়া যায়।

ইনপুট - N=300

আউটপুট - ৪

প্রোগ্রামে ব্যবহৃত পদ্ধতি

MaxPrime() ফাংশনে প্রথমে চেক করুন if (N < 2)। যদি সত্য হয় তবে শূন্য ফেরত দিন, অন্যথায় অগ্রসর হন।
এরপর দেওয়া সংখ্যা N-এর আগের সকল প্রাইম নম্বর বের করার জন্য এরাটোস্থেনিস সিভ (Sieve of Eratosthenes) ব্যবহার করুন।
pro=1 এবং max=0 নামক দুটি ইন্টিজার ভেরিয়েবল আরম্ভ করুন যথাক্রমে গুণফল এবং ফাইনাল আউটপুট সংরক্ষণের জন্য।
সিভের ভেতরে প্রথম সেট প্রাইম নম্বরগুলোর গুণফল N-এর চেয়ে ছোট থাকা পর্যন্ত গুণ করুন - pro *= p;
চেক করুন if (pro > N)। যদি সত্য হয় তবে max ফেরত দিন এবং max-এ ১ যোগ করুন।
সিভের বাইরেও max ফেরত দিন।

C++ প্রোগ্রাম উদাহরণ

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

int MaxPrime(int N){
    if (N < 2)
        return 0;
    // এরাটোস্থেনিস সিভ ব্যবহার
    bool Arr[N+1];
    memset(Arr, true, sizeof(Arr));
    int pro = 1, max = 0;
    for (int p=2; p*p<=N; p++){
        if (Arr[p] == true){
            for (int i=p*2; i<=N; i += p)
                Arr[i] = false;
            /*প্রথম সেট প্রাইম নম্বর গুণ করা যতক্ষণ না গুণফল N-এর চেয়ে ছোট থাকে*/
            pro *= p;
            if (pro > N)
                return max;
            max++;
        }
    }
    return max;
}

// মেইন ফাংশন
int main(){
    int N = 300;
    cout << MaxPrime(N);
    return 0;
}