এই সমস্যায়, আমাদের রেঞ্জ 1 <=arr[i] <=10 12 এর মধ্যে একটি অ্যারে দেওয়া হয়েছে . আমাদের কাজ হল অ্যারের সমস্ত উপাদানের LCM-এর সমস্ত প্রাইম ফ্যাক্টর প্রিন্ট করা।
আমাদের সমস্যা বোঝার জন্য একটি উদাহরণ নেওয়া যাক
Input: array = {2 , 5 , 15}
Output: 2 3 5
Explanation: LCM = 30
Factors of 30 = 2 * 3 * 5 এই সমস্যাটি সমাধান করার জন্য, আমাদের প্রথমে অ্যারে ডিজিটের LCM খুঁজে বের করতে হবে এবং তারপর LCM-এর ফ্যাক্টর খুঁজে বের করতে হবে এবং সমস্ত মৌলিক সংখ্যাকে প্রাইম করতে হবে।
কম্পাইলারের জন্য 10^6 ক্রম সংখ্যার LCM খুঁজে পেতে এটি কিছুটা ভারী হতে পারে। সুতরাং, আমরা এটি সমাধান করার জন্য অন্যান্য উপায় ব্যবহার করতে হবে।
আমরা ধারণাটি ব্যবহার করব যে সংখ্যার মৌলিক গুণনীয়কগুলিও তাদের LCM-এর মৌলিক গুণনীয়ক হবে। এর জন্য, আমরা মৌলিক ফ্যাক্টরাইজেশন ব্যবহার করব এবং সুন্দরম অ্যালগরিদমের চালনি ব্যবহার করে মৌলিক সংখ্যা খুঁজে বের করব।
এবং তারপর ফ্যাক্টর অ্যারে তৈরি করুন যাতে অ্যারের সংখ্যার 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
