इस समस्या में, हमें सीव O(log n) का उपयोग करके कई क्वेरीज़ के लिए अभाज्य गुणनखंडन की गणना करने के लिए एक प्रोग्राम बनाने की आवश्यकता है।
चूंकि सामान्य विधि O(sqrt(n) ) समय लेती है जो कई क्वेरीज़ के लिए आवश्यक समय को बहुत हद तक बढ़ा देती है।
आइए पहले पुनर्कथन करें,
अभाज्य गुणनखंडन एक संख्या में केवल अभाज्य गुणनखंड शामिल होते हैं, उन अभाज्य गुणनखंडों के कोई उत्पाद नहीं।
एराटोस्थनीज की छलनी (Sieve of 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
