이 글에서는 주어진 숫자의 가장 큰 소인수를 효율적으로 구하는 방법을 알아보겠습니다.
예를 들어 n = 1092라는 숫자가 있다고 가정해 보겠습니다. 1092의 소인수는 2, 2, 3, 7, 13이며, 따라서 가장 큰 소인수는 13입니다. 이 문제를 해결하기 위해서는 다음과 같은 규칙을 따라야 합니다.
숫자가 2로 나누어 떨어지면 최댓값(max)으로 2를 저장하고, 나누어 떨어지지 않을 때까지 숫자를 계속 2로 나눕니다.
이 과정을 거치면 남은 숫자는 반드시 홀수가 됩니다. 이제 3부터 숫자의 제곱근까지 2씩 증가시키며(홀수만 검사) 탐색합니다. 현재 값 i로 숫자가 나누어 떨어지면 max에 i를 저장하고, 숫자를 i로 나눈 값을 다시 대입한 뒤 같은 과정을 반복합니다.
마지막으로 남은 숫자가 2보다 크다면, 그 값은 더 이상 나눌 수 없는 소수이므로 그 자체가 가장 큰 소인수가 됩니다.
알고리즘을 살펴보면 더 쉽게 이해할 수 있습니다.
알고리즘
getMaxPrimeFactors(n)
begin
while n is divisible by 2, do
max := 2
n := n / 2
done
for i := 3 to √𝑛, increase i by 2, do
while n is divisible by i, do
max := i
n := n / i
done
done
if n > 2, then
max := n
end if
end
C 언어 구현 예제
#include<stdio.h>
#include<math.h>
int getMaxPrimeFactor(int n) {
int i, max = -1;
while(n % 2 == 0) {
max = 2;
n = n/2; // 2로 나누어 n의 값을 줄임
}
for(i = 3; i <= sqrt(n); i=i+2){ // 홀수만 검사하기 위해 i를 2씩 증가
while(n % i == 0) {
max = i;
n = n/i;
}
}
if(n > 2) {
max = n;
}
return max;
}
main() {
int n;
printf("Enter a number: ");
scanf("%d", &n);
printf("Max prime factor: %d", getMaxPrimeFactor(n));
}
실행 결과
Enter a number: 24024
Max prime factor: 13
동작 원리 정리
이 알고리즘이 효율적인 이유는 다음과 같습니다.
2를 먼저 제거: 짝수인 경우 2를 모두 나누어 제거하므로, 이후 검사는 홀수만 하면 됩니다.
제곱근까지만 검사: 어떤 수의 인수 중 하나는 반드시 제곱근 이하에 존재하므로, √n까지만 확인하면 충분합니다. 이를 통해 시간 복잡도를 O(√n) 수준으로 줄일 수 있습니다.
나눗셈으로 크기 축소: 인수를 찾을 때마다 n을 나누어 줄이기 때문에 검사 범위가 빠르게 감소합니다.
예를 들어 입력값이 24024인 경우, 24024 = 2 × 2 × 2 × 3 × 7 × 11 × 13으로 분해되므로 가장 큰 소인수 13이 출력됩니다.