C++로 숫자의 가장 큰 소인수(최대 소인수) 구하기

문제 개요

어떤 수 x가 주어졌을 때, x의 가장 큰 소인수(largest prime factor)를 구하는 것이 목표입니다. 예를 들어 x = 6이라면 소인수는 2와 3이므로 가장 큰 소인수는 3입니다.

이 문제는 수를 작은 약수부터 차례대로 나누어 소인수분해하면서, 지금까지 발견한 소인수 중 최댓값을 계속 추적하는 방식으로 간단하게 해결할 수 있습니다.

알고리즘 동작 방식

1. n이 2로 나누어떨어지는 동안 계속 2로 나누고, 최대 소인수(maxPF)를 2로 갱신합니다.
2. 3부터 √n까지의 홀수에 대해서만 검사합니다. 짝수 인수는 이미 앞 단계에서 모두 제거되었기 때문입니다.
3. i로 나누어떨어지는 동안 계속 나누고, maxPF를 i로 갱신합니다.
4. 반복이 끝난 후 남은 n이 2보다 크다면 그 값 자체가 소수이므로, maxPF를 n으로 설정합니다.

이 알고리즘의 시간 복잡도는 O(√n)으로 매우 효율적입니다.

예제 코드

#include <iostream>
#include <cmath>
using namespace std;
long long getMaxPrimefactor(long long n) {
    long long maxPF = -1;
    while (n % 2 == 0) {
        maxPF = 2;
        n /= 2;
    }
    for (int i = 3; i <= sqrt(n); i += 2) {
        while (n % i == 0) {
            maxPF = i;
            n = n / i;
        }
    }
    if (n > 2)
        maxPF = n;
    return maxPF;
}
int main() {
    long long n = 162378;
    cout << "Max Prime factor of " << n << " is " << getMaxPrimefactor(n);
}

실행 결과

Max Prime factor of 162378 is 97

동작 예시

n = 162378인 경우, 이 수는 2 × 3 × 3 × 3 × 31 × 97로 소인수분해됩니다. 따라서 프로그램이 출력하는 가장 큰 소인수는 97이 됩니다.