在这个问题中,我们得到的数组范围为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的素因。为此,我们将使用素数分解并使用Sundaram算法的筛子查找素数。
然后生成因子数组,其中将包含数组数字的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