अवधारणा
दी गई दो संख्याओं के संबंध में 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 से फिर से दोहराएं।
एराटोस्थनीज की चलनी विधि को लागू करने के बाद हम निम्नलिखित सूत्र को लागू करने के गुणनखंड में प्रमुख कारकों की संख्या की गणना कर सकते हैं -
प्राइमफैक्टर्स [संख्या] =प्राइमफैक्टर्स [संख्या / प्राइमडिविजर [संख्या]] + 1 वर्तमान में, कोई प्राइम फैक्टर के लिए उपसर्ग योग सरणी लागू कर सकता है और फिर अंतराल पर योग के लिए उत्तर दे सकता है [पी, क्यू]।
उदाहरण
// CPP program to find maximum
// number moves possible
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
// Used to store number of prime
// factors of each number
int primeFactors1[N];
// Shows Function to find number of prime
// factors of each number
void findPrimeFactors(){
for (int a = 2; a < N; a++)
// Now if a is a prime number
if (primeFactors1[a] == 0)
for (int b = a; b < N; b += a)
// Now increase value by one from
// it's preveious multiple
primeFactors1[b] = primeFactors1[b / a] + 1;
// Build prefix sum
// this will be helpful for
// multiple test cases
for (int a = 1; a < N; a++)
primeFactors1[a] += primeFactors1[a - 1];
}
// Driver Code
int main(){
// Create primeFactors1 array
findPrimeFactors();
int P = 7, Q = 4;
// required answer
cout << primeFactors1[P] - primeFactors1[Q];
return 0;
} आउटपुट
4