C++ में n! में अभाज्य संख्या p की घात खोजना

समस्या विवरण

इस समस्या में, हमें एक संख्या n और एक अभाज्य संख्या p दी गई है। हमारा कार्य n! में अभाज्य संख्या p की घात खोजना है।

उदाहरण

इनपुट: n = 6, p = 2
आउटपुट: 4

हल का दृष्टिकोण

समस्या का एक सरल समाधान n! का मान खोजना है। और फिर इसे फैक्टराइज़ करना, और फैक्टराइज़ेशन में अभाज्य संख्या p की घात खोजना।

यहां, संख्या को 5! = 30 में 2 की घात फैक्टराइज़ेशन के रूप में दर्शाया जा सकता है जो 3 है।

n फैक्टोरियल का मान है:

n! = n × (n-1) × (n-2) × ... × 2 × 1

n = 6 और p = 2 लें,

n! = 6! = 720
720 का फैक्टराइज़ेशन = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 2⁴ × 3² × 5
2 की घात 4 है।

कुशल दृष्टिकोण: लेगेंड्रे का सूत्र

n! में अभाज्य p का घात है:

exponent = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... (जब तक pᵏ ≤ n)

यह काम करता है क्योंकि: - प्रत्येक pवें संख्या में कम से कम एक p फैक्टर होता है - प्रत्येक p²वें संख्या में एक अतिरिक्त p फैक्टर होता है - प्रत्येक p³वें संख्या में एक और अतिरिक्त होता है, आदि।

C++ कार्यान्वयन

#include <iostream> 
using namespace std; 

int powerOfPrimeInFactorial(int N, int P) {
    int primePower = 0;
    long long factVal = P; // लॉन्ग लॉन्ग ओवरफ्लो से बचने के लिए
    
    while (factVal <= N) {
        primePower += N / factVal;
        factVal *= P;
    }
    return primePower;
}

int main() {
    int N = 6;
    int P = 2;
    cout << N << "! में अभाज्य संख्या " << P << " की घात है " 
         << powerOfPrimeInFactorial(N, P) << endl;
    return 0;
}

आउटपुट

6! में अभाज्य संख्या 2 की घात है 4

जटिलता विश्लेषण

• समय जटिलता: O(logₚ N) - बहुत तेज़
• स्पेस जटिलता: O(1)

उदाहरण ट्रेस (n=6, p=2)

factVal=2:  6/2 = 3  (2,4,6 में 2 का फैक्टर)
factVal=4:  6/4 = 1  (4 में अतिरिक्त 2)
factVal=8:  6/8 = 0  रुकें
कुल = 3 + 1 = 4 ✓

अनुप्रयोग

• निचले शून्यों की गिनती (p=5 के लिए)
• कॉम्बिनेटोरिक्स (nCr में अभाज्य घातांक)
• संख्या सिद्धांत समस्याएं