Các thừa số nguyên tố của LCM của các phần tử mảng trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng trong phạm vi 1 <=arr [i] <=10 ¹² . Nhiệm vụ của chúng ta là in tất cả các thừa số nguyên tố của LCM của tất cả các phần tử của mảng.

Hãy lấy một ví dụ để hiểu vấn đề của chúng ta

Input: array = {2 , 5 , 15}
Output: 2 3 5
Explanation: LCM = 30
Factors of 30 = 2 * 3 * 5

Để giải quyết vấn đề này, trước tiên chúng ta sẽ phải tìm LCM của các chữ số mảng, sau đó tìm các thừa số của LCM và nguyên tố tất cả các số nguyên tố.

Điều này có thể hơi nặng đối với trình biên dịch khi tìm LCM của các số có thứ tự 10 ^ 6. Vì vậy, chúng tôi sẽ phải sử dụng các cách khác để giải quyết nó.

Chúng ta sẽ sử dụng khái niệm rằng các thừa số nguyên tố của các số sau đó cũng sẽ là các thừa số nguyên tố của LCM của chúng. Đối với điều này, chúng tôi sẽ sử dụng thừa số nguyên tố và tìm các số nguyên tố bằng cách sử dụng sàng của thuật toán Sundaram.

Và sau đó tạo mảng thừa số sẽ chứa các thừa số nguyên tố của LCM trong số các số của mảng.

Chương trình cho thấy việc triển khai giải pháp của chúng tôi

Ví dụ

#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;
}

Đầu ra

Prime factors in the LCM of the numbers of the array are :
2  3   5