C++ में बड़ी संख्या के अभाज्य गुणनखंड और उनकी आवृत्ति

इस समस्या में, हमें एक पूर्णांक N ≤ 10¹⁸ दिया गया है। हमारा कार्य उस संख्या के सभी अभाज्य गुणनखंडों को उनकी घटित होने की आवृत्ति (frequency) के साथ प्रिंट करना है।

आइए एक उदाहरण से समझते हैं:

इनपुट: 100
आउटपुट: 2 2   5 2
व्याख्या: 100 का अभाज्य गुणनखंडन = 2 * 2 * 5 * 5।

इस समस्या को हल करने के लिए, हमें संख्या के अभाज्य गुणनखंड ढूंढने होंगे और फिर उनकी आवृत्तियों की गणना करनी होगी।

इसके लिए, हम पहले 2 की आवृत्ति की जांच करेंगे और संख्या को 2 से विभाजित करेंगे। फिर 3 से लेकर √n तक जांचेंगे। प्रत्येक अभाज्य संख्या जो संख्या का गुणनखंड है, उसे विभाजित करेंगे और उसकी आवृत्ति बढ़ाएंगे। जब संख्या 1 हो जाए तो रुक जाएंगे। फिर सभी अभाज्य संख्याओं को उनकी आवृत्तियों के साथ प्रिंट करेंगे।

नीचे दिए गए कोड में हमारे समाधान का कार्यान्वयन दिखाया गया है:

उदाहरण

#include <iostream>
#include <math.h>
using namespace std;

void factorize(long long n) {
    int count = 0;
    while (!(n % 2)) {
        n /= 2;
        count++;
    }
    if (count)
        cout << 2 << "\t" << count << endl;
    for (long long i = 3; i <= sqrt(n); i += 2) {
        count = 0;
        while (n % i == 0) {
            count++;
            n = n / i;
        }
        if (count)
            cout << i << "\t" << count << endl;
    }
    if (n > 2)
        cout << n << "\t" << 1 << endl;
}

int main() {
    long long N = 21000;
    cout << "संख्या " << N << " के अभाज्य गुणनखंड और उनकी आवृत्तियां हैं:\n";
    factorize(N);
    return 0;
}

आउटपुट

संख्या 21000 के अभाज्य गुणनखंड और उनकी आवृत्तियां हैं:
2   3
3   1
5   3
7   1