C++ में दो संख्याओं के सामान्य अभाज्य गुणनखंडों की गिनती करें

हमें दो संख्याएँ दी गई हैं, मान लीजिए x और y और कार्य दो संख्याओं के बीच सामान्य अभाज्य गुणनखंडों को खोजना है। सामान्य अभाज्य गुणनखंडों को पहले दो संख्याओं के बीच सामान्य संख्याओं की गणना करके और फिर सामान्य गुणनखंडों की सूची से उन संख्याओं की जांच करके पाया जा सकता है जो अभाज्य संख्याएं हैं।

उदाहरण के लिए

इनपुट - x = 10 y = 20 आउटपुट - दो संख्याओं के सामान्य अभाज्य गुणनखंड हैं: 2 5

व्याख्या - 10 और 20 के बीच सामान्य अभाज्य गुणनखंड केवल 2 और 5 हैं।

इनपुट - x = 34 y = 12 आउटपुट - दो संख्याओं के सामान्य अभाज्य गुणनखंड हैं: 2

व्याख्या - 34 और 12 के बीच सामान्य अभाज्य गुणनखंड 2 है।

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण

• दो संख्याओं x और y के मान इनपुट करें।

• एक फंक्शन बनाएं और एक फंक्शन के अंदर

• एक अस्थायी चर घोषित करें जो संख्याओं x और y का महत्तम सामान्य भाजक होगा

• 2 से शुरू होने वाला एक लूप बनाएं जब तक कि यह GCD से कम या बराबर है और i को बढ़ाएं

• लूप के अंदर जांचें कि क्या prime[i] && GCD%i = 0 है और यदि यह सही है

• i का मान प्रिंट करें

• परिणाम प्रिंट करें

उदाहरण

#include <bits/stdc++.h>
using namespace std;

#define MAX 100001
bool prime[MAX];

void SieveOfEratosthenes() {
    // एक बूलियन सरणी "prime[0..n]" बनाएं और आरंभ करें
    // सभी प्रविष्टियां true हैं। prime[i] में एक मान
    // अंततः false होगा यदि i अभाज्य नहीं है, अन्यथा true।
    memset(prime, true, sizeof(prime));
    // 0 और 1 अभाज्य संख्याएं नहीं हैं
    prime[0] = false;
    prime[1] = false;
    for (int p = 2; p * p <= MAX; p++) {
        // यदि prime[p] बदला नहीं गया है, तो यह अभाज्य है
        if (prime[p] == true) {
            // p के सभी गुणकों को गैर-अभाज्य के रूप में अपडेट करना
            for (int i = p * p; i <= MAX; i += p) {
                prime[i] = false;
            }
        }
    }
}

// सामान्य अभाज्य संख्याओं को खोजने के लिए फंक्शन
void common_prime(int x, int y) {
    // दी गई संख्याओं का GCD प्राप्त करें
    int g = __gcd(x, y);
    // g के अभाज्य भाजक खोजें
    for (int i = 2; i <= (g); i++) {
        // यदि i अभाज्य है और g का भाजक है
        if (prime[i] && g % i == 0) {
            cout << i << " ";
        }
    }
}

// मुख्य कोड
int main() {
    // सिव बनाना
    SieveOfEratosthenes();
    int x = 20, y = 30;
    cout << "Common prime factor of two numbers are: ";
    common_prime(x, y);
    return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा -

Common prime factor of two numbers are: 2 5