이 글에서는 하나의 숫자에 대한 모든 소인수(素因數)를 효율적으로 구하는 방법을 알아보겠습니다. 예를 들어 n = 1092가 주어졌다면, 1092의 소인수는 2, 2, 3, 7, 13입니다. 이 문제를 해결하려면 다음 두 가지 규칙을 따르면 됩니다.
숫자가 2로 나누어 떨어지면 2를 출력하고, 더 이상 나누어 떨어지지 않을 때까지 계속해서 2로 나눕니다.
이 과정이 끝나면 남은 숫자는 반드시 홀수입니다. 이제 3부터 해당 숫자의 제곱근(√n)까지 홀수만을 대상으로 반복하면서, 현재 값 i로 나누어 떨어지면 i를 출력하고 숫자를 i로 나눈 뒤 같은 과정을 반복합니다.
이 방식은 가능한 약수 후보를 √n까지만 확인하면 되므로, 단순히 1부터 n까지 전부 검사하는 방법보다 훨씬 빠릅니다. 시간 복잡도는 O(√n)입니다.
알고리즘
printPrimeFactors(n)
begin
while n is divisible by 2, do
print 2
n := n / 2
done
for i := 3 to √n, increase i by 2, do
while n is divisible by i, do
print i
n := n / i
done
done
if n > 2, then
print n
end if
end
C 언어 구현 예제
#include<stdio.h>
#include<math.h>
void primeFactors(int n) {
int i;
while(n % 2 == 0) {
printf("%d, ", 2);
n = n/2; // 2로 나누어 n 값을 줄임
}
for(i = 3; i <= sqrt(n); i=i+2){ // i를 2씩 증가시켜 홀수만 검사
while(n % i == 0) {
printf("%d, ", i);
n = n/i;
}
}
if(n > 2) {
printf("%d, ", n);
}
}
main() {
int n;
printf("Enter a number: ");
scanf("%d", &n);
primeFactors(n);
}
실행 결과
Enter a number: 24024
2, 2, 2, 3, 7, 11, 13,
동작 원리 정리
위 코드의 마지막 부분에서 n > 2 조건 검사가 필요한 이유는 다음과 같습니다. 3부터 √n까지의 모든 나눗셈이 끝난 후에도 n이 1보다 크게 남아 있다면, 그 값 자체가 소수라는 의미입니다. 예를 들어 입력값이 17처럼 소수인 경우, 어떤 수로도 나누어 떨어지지 않으므로 마지막에 n 자체를 소인수로 출력해야 합니다.
또한 반복문에서 i를 1씩이 아닌 2씩 증가시키는 이유는, 2를 제외한 모든 짝수는 소수가 아니기 때문입니다. 이미 2로 나누는 작업을 먼저 완료했으므로, 이후에는 홀수만 검사해도 누락되는 소인수가 없습니다. 이러한 최적화를 통해 불필요한 연산을 절반 가까이 줄일 수 있습니다.