এই সমস্যায়, 1 ≤ arr[i] ≤ 10¹² রেঞ্জের একটি অ্যারে দেওয়া আছে। আমাদের কাজ হলো অ্যারের সব 엘িমেন্টের LCM-এর সকল প্রাইম ফ্যাক্টর প্রিন্ট করা।
উদাহরণ:
ইনপুট: array = {2, 5, 15} আউটপুট: 2 3 5 ব্যাখ্যা: LCM = 30, 30-এর ফ্যাক্টর = 2 * 3 * 5
সাধারণভাবে LCM বের করে তার ফ্যাক্টর খুঁজতে বড় সংখ্যায় কম্পাইলারের জন্য কষ্টসাধ্য হয়। তাই আমরা অন্য পদ্ধতি ব্যবহার করব: যেকোনো সংখ্যাগুলোর প্রাইম ফ্যাক্টর তাদের LCM-এরও প্রাইম ফ্যাক্টর হবে। এই ধারণা ব্যবহার করে সিভ অফ সুন্দরাম (Sieve of Sundaram) দিয়ে প্রাইম নম্বর বের করে ফ্যাক্টর অ্যারে তৈরি করব।
উদাহরণ
#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 << "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
