C++ में N को 1 तक कम करने के लिए अधिकतम ऑपरेशन खोजें

अवधारणा

दो दी गई संख्याओं P और Q (P और Q 10^6 तक हो सकते हैं) के संबंध में जो एक संख्या N = (P!/Q!) बनाती हैं। हमारा कार्य N को 1 तक संभावित अधिकतम संख्या में ऑपरेशन करके कम करना है। याद रखें, प्रत्येक ऑपरेशन में, कोई N को N/X से बदल सकता है यदि N, X से विभाज्य है। उन अधिकतम ऑपरेशनों की संख्या निर्धारित करें जो संभव हो सकते हैं।

इनपुट

A = 7, B = 4

आउटपुट

4

व्याख्या

N 210 है और भाजक 2, 3, 5, 7 हैं

इनपुट

A = 3, B = 1

आउटपुट

2

व्याख्या

N 6 है और भाजक 2,3 हैं।

विधि

यह देखा गया है कि संख्या P!/Q! का गुणनखंडन संख्याओं (Q + 1)*(Q + 2)*…*(P – 1)*P के गुणनखंडन के समान है।

यह भी ध्यान दिया जाना चाहिए कि ऑपरेशनों की संख्या अधिकतम होगी यदि हम N को केवल उसके अभाज्य गुणनखंडों से विभाजित करते हैं। इसके परिणामस्वरूप, दूसरे शब्दों में हमें N के अभाज्य गुणनखंडों की गिनती निर्धारित करने की आवश्यकता है जिसमें डुप्लिकेट भी शामिल हैं।

2 से 1000000 तक की प्रत्येक संख्या के गुणनखंडन में अभाज्य गुणनखंडों की संख्या गिनने की कल्पना करें।

सबसे पहले, एराटोस्थनीज की छलनी लागू करें ताकि इन संख्याओं में से प्रत्येक का एक अभाज्य भाजक निर्धारित किया जा सके। यह निम्नानुसार समझाया गया है −

• 2 से N तक लगातार पूर्णांकों की एक सूची बनाएं: (2, 3, 4, …, N)।

• सबसे पहले, p को 2 मान लें, पहली अभाज्य संख्या।

• p^2 से शुरू करके, p की वृद्धि में गिनती करें और सूची में p^2 से बड़ी या बराबर इनमें से प्रत्येक संख्या को इंगित करें। तो, ये संख्याएं p(p+1), p(p+2), p(p+3), आदि हो सकती हैं।

• सूची में p से बड़ी पहली संख्या निर्धारित करें जो इंगित नहीं है। यह देखा गया है कि यदि ऐसी कोई संख्या नहीं थी, तो रुक जाएं। अन्यथा, p को अब इस संख्या के बराबर मान लें (जो अगली अभाज्य संख्या को इंगित करता है), और चरण 3 से फिर से दोहराएं।

एराटोस्थनीज की छलनी विधि लागू करने के बाद हम निम्न सूत्र को लागू करके एक संख्या के गुणनखंडन में अभाज्य गुणनखंडों की संख्या की गणना कर सकते हैं −

primefactors[num] = primefactors[num / primedivisor[num]] + 1 वर्तमान में, कोई अभाज्य गुणनखंडों के लिए उपसर्ग योग सरणी लागू कर सकता है और फिर अंतराल [P, Q] पर योग के लिए उत्तर दे सकता है।

उदाहरण

// CPP program to find maximum // number moves possible #include <bits/stdc++.h> using namespace std; #define N 1000005 // प्रत्येक संख्या के अभाज्य // गुणनखंडों की संख्या संग्रहीत करने के लिए उपयोग किया जाता है int primeFactors1[N]; // प्रत्येक संख्या के अभाज्य // गुणनखंडों की संख्या खोजने वाला फ़ंक्शन void findPrimeFactors(){    for (int a = 2; a < N; a++)    // अब यदि a एक अभाज्य संख्या है    if (primeFactors1[a] == 0)       for (int b = a; b < N; b += a)          // अब इसके पिछले गुणक से          // मान को एक से बढ़ाएं    primeFactors1[b] = primeFactors1[b / a] + 1;    // उपसर्ग योग बनाएं    // यह कई टेस्ट केस के लिए    // सहायक होगा    for (int a = 1; a < N; a++)       primeFactors1[a] += primeFactors1[a - 1]; } // ड्राइवर कोड int main(){    // primeFactors1 सरणी बनाएं    findPrimeFactors();    int P = 7, Q = 4;    // आवश्यक उत्तर    cout << primeFactors1[P] - primeFactors1[Q];    return 0; }

आउटपुट

4