이 문제에서는 최대 1018까지의 매우 큰 정수 N이 주어집니다. 우리가 해야 할 일은 이 수를 구성하는 모든 소인수(prime factor)와 각 소인수가 등장하는 빈도를 함께 출력하는 것입니다.
먼저 예제를 통해 문제를 이해해 보겠습니다.
입력: 100
출력: 2 2
5 2
설명: 100 = 2 × 2 × 5 × 5 이므로,
소인수 2는 2번, 소인수 5는 2번 등장합니다.문제 해결 접근 방식
이 문제를 해결하려면 주어진 수의 소인수들을 찾은 뒤, 각 소인수가 몇 번 곱해졌는지(빈도)를 계산해야 합니다. 알고리즘은 다음과 같이 진행됩니다.
- 먼저 인수 2의 개수를 확인하고, 나눌 수 없을 때까지 수를 2로 계속 나눕니다.
- 이후 3부터 √n(제곱근)까지 홀수만 검사하면서, 해당 값으로 나누어 떨어질 때마다 나누고 빈도를 1씩 증가시킵니다.
- 나누어지는 수가 1이 되면 반복을 종료합니다.
- 마지막에 남은 값이 2보다 크다면 그 자체가 소수이므로 빈도 1과 함께 출력합니다.
√n까지만 검사해도 충분한 이유는, 어떤 합성수의 소인수 중 하나는 반드시 제곱근 이하에 존재하기 때문입니다. 이 덕분에 1018처럼 큰 수도 효율적으로 처리할 수 있습니다.
C++ 구현 코드
아래 코드는 위 알고리즘을 구현한 예제입니다.
#include <iostream>
#include <math.h>
using namespace std;
void factorize(long long n){
int count = 0;
while (!(n % 2)) {
n/= 2;
count++;
}
if (count)
cout<<2<<"\t"<<count<<endl;
for (long long i = 3; i <= sqrt(n); i += 2) {
count = 0;
while (n % i == 0) {
count++;
n = n / i;
}
if (count)
cout<<i<<"\t"<<count<<endl;
}
if (n > 2)
cout<<n<<"\t"<<1<<endl;
}
int main() {
long long N = 21000;
cout<<"The prime factors and their frequencies of the number "<<N<<" are \n";
factorize(N);
return 0;
}실행 결과
The prime factors and their frequencies of the number 21000 are 2 3 3 1 5 3 7 1
코드 설명 및 시간 복잡도
21000은 2³ × 3¹ × 5³ × 7¹로 분해되므로, 위 실행 결과에서 각 소인수 옆의 숫자가 곧 해당 소인수의 빈도임을 확인할 수 있습니다.
factorize()함수는 먼저 2로 나누어 떨어지는 동안 반복하여 2의 지수를 구합니다.- 그다음 3부터 √n까지 홀수만 검사하며, 나누어 떨어지는 동안 계속 나누고 빈도를 기록합니다.
- 루프가 끝난 후 남은 값이 2보다 크면 그 값은 소수이므로 빈도 1로 출력합니다.
이 알고리즘의 시간 복잡도는 O(√n)입니다. 따라서 1018 크기의 수라도 약 10억 번의 연산 내에서 처리할 수 있어, 일반적인 시험용 범위에서는 충분히 실용적인 속도를 보여줍니다. 다만 더 큰 수나 극단적인 성능이 필요한 경우에는 폴라드 로(Pollard's rho) 알고리즘 같은 고급 소인수분해 기법을 고려할 수 있습니다.