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

इस समस्या में, हमें एक सरणी दी गई है जिसकी सीमा 1 ≤ arr[i] ≤ 10¹² है। हमारा कार्य सरणी के सभी तत्वों के LCM (लघुत्तम समापवर्त्य) के सभी अभाज्य गुणनखंडों को प्रिंट करना है।

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

इनपुट: सरणी = {2, 5, 15}
आउटपुट: 2 3 5
व्याख्या: LCM = 30, 30 के गुणनखंड = 2 * 3 * 5

इस समस्या को हल करने के लिए, हमें पहले सरणी के तत्वों का LCM निकालना होगा और फिर LCM के गुणनखंडों में से अभाज्य संख्याओं को छांटना होगा।

10⁶ क्रम की संख्याओं का LCM निकालना कंपाइलर के लिए भारी हो सकता है। इसलिए हमें अन्य तरीकों का उपयोग करना होगा।

हम इस अवधारणा का उपयोग करेंगे कि संख्याओं के अभाज्य गुणनखंड उनके LCM के भी अभाज्य गुणनखंड होंगे। इसके लिए, हम अभाज्य गुणनखंडन का उपयोग करेंगे और सुंदरम की छलनी (Sieve of Sundaram) एल्गोरिदम से अभाज्य संख्याएं खोजेंगे।

फिर एक गुणनखंड सरणी बनाएंगे जिसमें सरणी की संख्याओं के LCM के अभाज्य गुणनखंड होंगे।

उदाहरण

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

const int MAX = 1000000;
typedef long long int ll;
vector <int> primeNumbers;

void findPrimeNumbers() {
    int n = MAX;
    int nNew = (n)/2;
    bool marked[nNew + 100];
    memset(marked, false, sizeof(marked));
    int tmp = sqrt(n);
    for (int i=1; i<=(tmp-1)/2; i++)
        for (int j=(i*(i+1))<<1; j<=nNew; j=j+2*i+1)
            marked[j] = true;
    primeNumbers.push_back(2);
    for (int i=1; i<=nNew; i++)
        if (marked[i] == false)
            primeNumbers.push_back(2*i + 1);
}

void printPrimeLCM(ll arr[], int n) {
    findPrimeNumbers();
    int factors[MAX] = {0};
    for (int i=0; i 1)
            factors[copy] = 1;
    }
    if (factors[2] == 1)
        cout << 2 << "\t";
    for (int i=3; i<=MAX; i=i+2)
        if (factors[i] == 1)
            cout << i << "\t";
}

int main() {
    ll arr[] = {20, 10, 15, 60};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "सरणी की संख्याओं के LCM में अभाज्य गुणनखंड हैं:\n";
    printPrimeLCM(arr, n);
    return 0;
}

आउटपुट

सरणी की संख्याओं के LCM में अभाज्य गुणनखंड हैं:
2 3 5