이 문제에서는 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