C++로 숫자의 모든 소인수와 거듭제곱(지수) 출력하기

문제 개요

이 문제에서는 하나의 수 N이 주어지며, N을 나누는 모든 고유한 소인수(prime factor)와 각 소인수의 거듭제곱(지수)을 찾아 출력해야 합니다.

예시를 통해 살펴보겠습니다.

입력: 55
출력:
5 → 지수 1
11 → 지수 1

설명: 55는 5와 11로 나누어 떨어지며, 두 소인수 모두 한 번씩만 곱해지므로 지수는 각각 1입니다.

이 문제를 해결하는 가장 기본적인 접근 방법은 먼저 N의 소인수를 구한 뒤, 각 소인수가 N을 몇 번이나 나눌 수 있는지(즉, 거듭제곱)를 계산하여 출력하는 것입니다.

알고리즘 — 효율적인 접근 방식

1단계: 크기가 N+1인 배열 s를 생성합니다.
       s[i]에는 i를 나누는 가장 작은 소인수가 저장됩니다.
2단계: prime = s[N], power = 1로 초기화합니다.
3단계: N이 1보다 큰 동안 반복합니다.
   3-1. N을 s[N]으로 나눕니다. (N /= s[N])
   3-2. prime == s[N]이라면 power를 1 증가시킵니다.
4단계: prime과 power를 출력합니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
void primes(int N, int s[]){
    vector <bool> prime(N+1, false);
    for (int i=2; i<=N; i+=2)
        s[i] = 2;
    for (int i=3; i<=N; i+=2){
        if (prime[i] == false){
            s[i] = i;
            for (int j=i; j*i<=N; j+=2){
                if (prime[i*j] == false){
                    prime[i*j] = true;
                    s[i*j] = i;
                }
            }
        }
    }
}
void generatePrimeFactors(int N) {
    int s[N+1];
    primes(N, s);
    cout<<"Factor\tPower"<<endl;
    int prime = s[N];
    int power = 1;
    while (N > 1){
        N /= s[N];
        if (prime == s[N]){
            power++;
            continue;
        }
        cout<<prime<<"\t"<<power<<endl;
        prime = s[N];
        power = 1;
    }
}
int main() {
    int N = 55;
    cout<<"The prime factors are and their powers are :\n";
    generatePrimeFactors(N);
    return 0;
}

코드 설명

primes() 함수는 에라토스테네스의 체와 유사한 방식으로, 2부터 N까지 각 수의 가장 작은 소인수를 배열 s에 미리 계산해 둡니다. 짝수는 모두 2를 저장하고, 홀수 중 합성수는 해당 수를 처음으로 나누는 소수를 저장합니다.

generatePrimeFactors() 함수는 이 배열을 활용해 N을 반복적으로 나누면서 소인수분해를 진행합니다. 같은 소인수가 연속해서 나타나면 지수(power)를 증가시키고, 새로운 소인수가 등장하면 이전 소인수와 지수를 출력한 뒤 값을 초기화합니다. 전처리 과정의 시간 복잡도는 O(N log log N)으로, 이후 소인수분해 자체는 매우 빠르게 수행됩니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

The prime factors are and their powers are :
Factor Power
5 1
11 1