C++로 배열 요소들의 최소공배수(LCM) 소인수 구하기

이 문제에서는 각 요소가 1 ≤ arr[i] ≤ 10¹² 범위에 있는 배열이 주어집니다. 우리의 목표는 배열의 모든 요소에 대한 최소공배수(LCM)의 모든 소인수를 출력하는 것입니다.

문제 이해하기

간단한 예제를 통해 문제를 살펴보겠습니다.

입력: array = {2 , 5 , 15}
출력: 2 3 5
설명: LCM = 30
30의 인수 = 2 × 3 × 5

배열 {2, 5, 15}의 최소공배수는 30이며, 30을 소인수분해하면 2 × 3 × 5가 됩니다. 따라서 정답은 2, 3, 5입니다.

접근 방법

가장 직관적인 방법은 먼저 배열 요소들의 LCM을 구한 뒤, 그 LCM의 약수를 구하고 그중에서 소수만 걸러내는 것입니다.

하지만 배열 요소가 최대 10¹²까지 가능하기 때문에, LCM 자체가 매우 커질 수 있습니다. 이렇게 큰 수의 LCM을 직접 계산하면 오버플로우와 성능 저하 문제가 발생하여 비효율적입니다. 따라서 다른 방식으로 접근해야 합니다.

핵심 아이디어

여기서 중요한 수학적 성질 하나를 활용합니다.

“어떤 수들의 소인수는 그 수들의 LCM의 소인수이기도 하다”

즉, LCM을 직접 구할 필요 없이 배열의 각 요소를 개별적으로 소인수분해한 후 등장하는 소수들을 모두 모으면, 그것이 곧 LCM의 소인수 집합이 됩니다. 이때 소수 목록은 Sundaram의 체(Sieve of Sundaram) 알고리즘을 이용해 미리 생성합니다.

전체 과정을 정리하면 다음과 같습니다.

Sundaram의 체를 이용해 필요한 범위(√10¹² = 10⁶) 이하의 모든 소수를 미리 구합니다.
배열의 각 요소를 순회하며 소인수분해를 수행합니다.
발견된 각 소인수를 factors 배열에 표시합니다.
마지막으로 factors 배열에서 표시된 소수들을 모두 출력합니다.

C++ 구현 코드

#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

코드 설명

1. findPrimeNumbers()

Sundaram의 체 알고리즘을 사용하여 10⁶ 이하의 모든 소수를 생성합니다. 이 알고리즘은 홀수만 대상으로 합성수를 표시하기 때문에 일반적인 에라토스테네스의 체보다 메모리를 절반 수준으로 줄일 수 있습니다.

2. printPrimeLCM()

배열의 각 요소에 대해 √arr[i] 이하의 소수들로 나누어 소인수분해를 진행합니다. 특정 소수로 나누어떨어지면 해당 소수를 factors 배열에 표시하고, 더 이상 나누어떨어지지 않을 때까지 반복해서 나눕니다.

모든 소수 검사가 끝난 후 남은 값이 1보다 크다면, 그 값 자체가 소인수이므로 이 역시 factors 배열에 표시합니다.

3. 결과 출력

factors 배열을 순회하면서 표시된(값이 1인) 소수들을 차례대로 출력합니다. 짝수인 소수는 2뿐이므로 2를 먼저 처리하고, 이후에는 홀수만 검사하여 효율성을 높였습니다.

복잡도 분석

시간 복잡도: 소수 생성에 O(N log log N), 각 배열 요소의 소인수분해에 약 O(√M / log √M)이 소요됩니다. 여기서 N은 체의 크기, M은 배열 요소의 최댓값입니다.
공간 복잡도: 소수 목록과 factors 배열 저장을 위해 O(MAX)의 공간이 필요합니다.

이처럼 LCM을 직접 계산하지 않고 각 요소의 소인수를 결합하는 방식을 사용하면, 매우 큰 수가 포함된 배열에서도 오버플로우 없이 안정적으로 LCM의 소인수를 구할 수 있습니다.