이 문제는 여러 개의 쿼리에 대해 에라토스테네스의 체(Sieve)를 이용해 O(log n) 시간 안에 소인수 분해를 수행하는 프로그램을 작성하는 것입니다.
일반적인 소인수 분해 방법은 숫자 하나당 O(√n)의 시간이 소요됩니다. 따라서 쿼리 개수가 많아지면 전체 실행 시간이 기하급수적으로 늘어나 비효율적입니다. 이를 개선하려면 사전 계산(전처리)을 통해 각 쿼리를 훨씬 빠르게 처리해야 합니다.
기본 개념 정리
소인수 분해(Prime Factorization)란 어떤 수를 소수들의 곱으로 나타내는 것을 말합니다. 이때 포함되는 것은 오직 소수 인수뿐이며, 그 곱으로 만들어지는 합성수는 포함되지 않습니다.
에라토스테네스의 체(Sieve of Eratosthenes)는 주어진 범위 내의 모든 소수를 효율적으로 찾아내는 고전적인 알고리즘입니다. 이 글에서는 단순히 소수를 구하는 데 그치지 않고, 체를 변형하여 각 수의 최소 소인수(Smallest Prime Factor, SPF)를 미리 저장하는 데 활용합니다.
해결 접근 방식
핵심 아이디어는 다음과 같습니다.
- 주어진 범위까지 에라토스테네스의 체를 변형해, 모든 수에 대해 최소 소인수를 미리 계산해 배열에 저장합니다.
- 소인수 분해할 수가 주어지면, 해당 수의 최소 소인수를 찾아 기록하고, 그 수를 이 인수로 나눕니다.
- 나눈 결과가 1이 될 때까지 이 과정을 반복합니다. 수가 1이 되었다는 것은 더 이상 남은 인수가 없음을 의미합니다.
체를 사용하면 어떤 수의 최소 소인수를 O(1)에 바로 조회할 수 있으므로, 한 번의 소인수 분해는 최대 O(log n)번의 나눗셈만으로 완료됩니다. 전처리에 O(n log log n)의 시간이 들지만, 이후에는 여러 쿼리를 각각 O(log n)에 처리할 수 있어 쿼리가 많은 상황에서 매우 효율적입니다.
예제 코드
다음은 위 접근 방식을 C++로 구현한 프로그램입니다.
#include <iostream>
using namespace std;
int primes[100001];
void sieveOfEratosthenes(int N) {
N+=2;
primes[1] = 1;
for (int i=2; i<N; i++)
primes[i] = i;
for (int i=4; i<N; i+=2)
primes[i] = 2;
for (int i=3; i*i<N; i++) {
if (primes[i] == i) {
for (int j=i*i; j<N; j+=i)
if (primes[j]==j)
primes[j] = i;
}
}
}
void findPrimeFactors(int num) {
sieveOfEratosthenes(num);
int factor;
while (num != 1) {
factor = primes[num];
cout<<factor<<" ";
num /= factor;
}
}
int main() {
int N = 45214;
cout<<"Prime factorization of the number "<<N<<" using sieve is ";
findPrimeFactors(N);
return 0;
}
출력 결과
Prime factorization of the number 45214 using sieve is 2 13 37 47
실행 결과, 45214는 2 × 13 × 37 × 47로 소인수 분해됩니다. 실제 서비스에서는 여러 쿼리를 처리하기 전에 체를 한 번만 생성해 두고 재사용하는 것이 좋습니다. 매 쿼리마다 체를 다시 만들면 전처리 비용이 반복되어 성능 이점이 사라질 수 있습니다.