सी ++ में एकाधिक प्रश्नों के लिए चलनी ओ (लॉग एन) का उपयोग कर प्राइम फैक्टराइजेशन

इस समस्या में, हमें कई प्रश्नों के लिए चलनी ओ (लॉग एन) का उपयोग करके प्राइम फैक्टराइजेशन की गणना करने के लिए एक प्रोग्राम बनाने की आवश्यकता है।

जैसा कि सामान्य विधि में O(sqrt(n) ) समय लगता है जो कई प्रश्नों से आवश्यक समय को काफी हद तक बढ़ा देगा।

आइए पहले पुनर्कथन करें,

प्राइम फ़ैक्टराइज़ेशन किसी संख्या में केवल अभाज्य गुणनखंड शामिल होते हैं, उन अभाज्य गुणनखंडों का कोई उत्पाद नहीं।

इराटोस्थनीज की छलनी दी गई सीमा के भीतर सभी अभाज्य संख्याओं को उत्पन्न करने के लिए एक एल्गोरिथम है।

समाधान दृष्टिकोण

समस्या का समाधान संख्या को विभाजित करने वाले सबसे छोटे गुणनखंड को ढूंढकर, गुणनखंड के रूप में सहेज कर और गुणनखंड से विभाजित करके संख्या को अद्यतन करके प्राप्त किया जाता है। यह प्रक्रिया पुनरावर्ती रूप से तब तक की जाती है जब तक कि विभाजन के बाद संख्या 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