C++로 [1, N] 범위에서 가질 수 있는 서로 다른 소인수의 최대 개수 구하기

문제 개요

주어진 문제는 [1, N] 범위 안의 숫자가 가질 수 있는 서로 다른 소인수(unique prime factors)의 최대 개수를 찾는 것입니다.

예제로 이해하기

입력 − N = 100

출력 − 3

설명 − [1, 100] 범위에 속한 수 30을 살펴보겠습니다.

30 = 2 × 3 × 5 이므로 서로 다른 소인수는 총 3개입니다. 따라서 [1, 100] 범위에서 나타날 수 있는 서로 다른 소인수의 최대 개수는 3입니다.

입력 − N = 300

출력 − 4

해결 접근 방식

핵심 아이디어는 간단합니다. k개의 서로 다른 소인수를 가지는 가장 작은 수는 '가장 작은 k개의 소수를 모두 곱한 값'입니다. 예를 들어 2 × 3 × 5 = 30이 세 개의 서로 다른 소인수를 가지는 가장 작은 수입니다. 따라서 소수를 차례대로 곱해가다가 곱이 N을 초과하는 순간 직전까지의 소수 개수가 곧 정답이 됩니다.

MaxPrime() 함수에서 먼저 N < 2인지 확인합니다. 조건이 참이면 0을 바로 반환하고, 그렇지 않으면 다음 단계로 진행합니다.
에라토스테네스의 체(Sieve of Eratosthenes)를 사용하여 N 이하의 모든 소수를 찾아냅니다.
소수들의 곱을 저장할 pro와 최종 답을 저장할 max 두 개의 int형 변수를 각각 1과 0으로 초기화합니다.
체를 순회하면서 곱이 N보다 작게 유지되는 동안 앞쪽 소수들을 계속 곱합니다 (pro *= p).
pro > N이라면 현재 max 값을 즉시 반환하고, 그렇지 않으면 max에 1을 더합니다.
체 순회가 끝난 후에도 마지막으로 max를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int MaxPrime(int N){
    if (N < 2)
        return 0;
    // 에라토스테네스의 체 사용
    bool Arr[N+1];
    memset(Arr, true, sizeof(Arr));
    int pro = 1, max = 0;
    for (int p=2; p*p<=N; p++){
        if (Arr[p] == true){
            for (int i=p*2; i<=N; i += p)
                Arr[i] = false;
            /* 곱이 N보다 작은 동안 앞쪽 소수들을 곱함 */
            pro *= p;
            if (pro > N)
                return max;
            max++;
        }
    }
    return max;
}
// 메인 함수
int main(){
    int N = 300;
    cout << MaxPrime(N);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻습니다 −

복잡도 분석

에라토스테네스의 체 기반으로 동작하므로 시간 복잡도는 O(N log log N), 공간 복잡도는 소수 여부를 저장하는 배열 때문에 O(N)입니다. N이 커져도 효율적으로 동작하는 것이 이 방법의 장점입니다.