इस समस्या में, हमें 1 <=arr[i] <=10 12 की सीमा के भीतर एक सरणी दी जाती है। . हमारा काम सरणी के सभी तत्वों के एलसीएम के सभी प्रमुख कारकों को प्रिंट करना है।
हमारी समस्या को समझने के लिए एक उदाहरण लेते हैं
Input: array = {2 , 5 , 15}
Output: 2 3 5
Explanation: LCM = 30
Factors of 30 = 2 * 3 * 5 इस समस्या को हल करने के लिए, हमें पहले सरणी अंकों का एलसीएम खोजना होगा और फिर एलसीएम के गुणनखंडों को खोजना होगा और सभी अभाज्य संख्याओं को अभाज्य बनाना होगा।
यह संकलक के लिए क्रम 10^6 की संख्या के एलसीएम को खोजने के लिए थोड़ा भारी हो सकता है। इसलिए, हम इसे हल करने के लिए अन्य तरीकों का उपयोग करेंगे।
हम इस अवधारणा का उपयोग करेंगे कि संख्याओं के अभाज्य गुणनखंड भी उनके 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<n; i++) {
ll copy = arr[i];
int sqr = sqrt(copy);
for (int j=0; primeNumbers[j]<=sqr; j++){
if (copy%primeNumbers[j] == 0){
while (copy%primeNumbers[j] == 0)
copy = copy/primeNumbers[j];
factors[primeNumbers[j]] = 1;
}
}
if (copy > 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<<"Prime factors in the LCM of the numbers of the array are :\n";
printPrimeLCM(arr, n);
return 0;
} आउटपुट
Prime factors in the LCM of the numbers of the array are : 2 3 5