এই সমস্যায় আমাদের সিভ ব্যবহার করে প্রাইম ফ্যাক্টরাইজেশন O(log n) একাধিক কোয়েরির জন্য ক্যালকুলেট করার প্রোগ্রাম তৈরি করতে হবে।
সাধারণ পদ্ধতিতে O(sqrt(n)) সময় লাগে যা একাধিক কোয়েরির জন্য সময় অনেক বেড়া দেয়।
আসুন প্রথমে রিক্যাপ করি,
প্রাইম ফ্যাক্টরাইজেশন হলো একটি সংখ্যার শুধু প্রাইম ফ্যাক্টরগুলো, তাদের গুণফলের ফ্যাক্টরগুলো নয়।
এراتোস্থেনিসের সিভ হলো একটি এলগরিদম যা দেওয়া রেঞ্জের সব প্রাইম সংখ্যা জেনারেট করে।
সমাধানের পদ্ধতি
সমস্যার সমাধান হলো সংখ্যাকে ভাগ করার সর্বোচ্চ ছোট ফ্যাক্টর খুঁজে বের করা, সেটিকে ফ্যাক্টর হিসেবে সংরক্ষণ করা এবং সংখ্যাকে সেই ফ্যাক্টর দিয়ে ভাগ করে আপডেট করা। এই প্রক্রিয়া রিকারসিভভাবে চলবে যতক্ষণ না সংখ্যা ১ হয়ে যায়, মানে আর কোনো ফ্যাক্টর সম্ভব নয়।
গণনাটি এراتোস্থেনিসের সিভ ব্যবহার করে করা হয় যা সর্বোচ্চ ছোট প্রাইম ফ্যাক্টর খুঁজে বের করার টাইম কমপ্লেক্সিটি কমানোয়।
আমাদের সমাধান দেখানোর প্রোগ্রাম
উদাহরণ
#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
