C++の配列要素のLCMの素因数

この問題では、1 <=arr [i] <=10 ¹² の範囲内の配列が与えられます。 。私たちのタスクは、配列のすべての要素の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