এই সমস্যায়, একাধিক প্রশ্নের জন্য Sieve O(log n) ব্যবহার করে প্রাইম ফ্যাক্টরাইজেশন গণনা করার জন্য আমাদের একটি প্রোগ্রাম তৈরি করতে হবে।
যেহেতু সাধারণ পদ্ধতিতে O(sqrt(n) ) সময় লাগে যা একাধিক প্রশ্ন থেকে প্রয়োজনীয় সময়কে অনেকাংশে বাড়িয়ে দেবে।
প্রথমে সংক্ষিপ্ত করা যাক,
প্রধান ফ্যাক্টরাইজেশন একটি সংখ্যার মধ্যে শুধুমাত্র মৌলিক গুণনীয়কগুলি অন্তর্ভুক্ত থাকে, সেই মৌলিক গুণনীয়কগুলির কোনো পণ্য নয়৷
Eratosthenes চালনি প্রদত্ত সীমার মধ্যে সমস্ত মৌলিক সংখ্যা তৈরি করার জন্য একটি অ্যালগরিদম।
সমাধান পদ্ধতি
সংখ্যাটিকে ভাগ করে এমন ক্ষুদ্রতম গুণনীয়কটি খুঁজে বের করে, এটিকে একটি গুণনীয়ক হিসাবে সংরক্ষণ করে এবং গুণনীয়ক দ্বারা ভাগ করে সংখ্যাটি আপডেট করে সমস্যার সমাধান পাওয়া যায়। এই প্রক্রিয়াটি পুনরাবৃত্তভাবে করা হয় যতক্ষণ না বিভাজনের পরে সংখ্যাটি 1 হয়ে যায়, যার মানে অন্য কোনো কারণ সম্ভব নয়।
গণনা করা হয় ইরাটোসথেনিসের চালনি ব্যবহার করে যা ক্ষুদ্রতম প্রাইম ফ্যাক্টর খোঁজার সময় জটিলতা কমায়।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
উদাহরণ
#include <iostream>
using namespace std;
int primes[100001];
void sieveOfEratosthenes(int N) {
N+=2;
primes[1] = 1;
for (int i=2; i<N; i++)
primes[i] = i;
for (int i=4; i<N; i+=2)
primes[i] = 2;
for (int i=3; i*i<N; i++) {
if (primes[i] == i) {
for (int j=i*i; j<N; j+=i)
if (primes[j]==j)
primes[j] = i;
}
}
}
void findPrimeFactors(int num) {
sieveOfEratosthenes(num);
int factor;
while (num != 1) {
factor = primes[num];
cout<<factor<<" ";
num /= factor;
}
}
int main() {
int N = 45214;
cout<<"Prime factorization of the number "<<N<<" using sieve is ";
findPrimeFactors(N);
return 0;
} আউটপুট
Prime factorization of the number 45214 using sieve is 2 13 37 47
