소인수(Prime Factor)란 주어진 수의 인수 중에서 소수에 해당하는 수를 말합니다.
약수(Factor)는 곱셈을 통해 주어진 수를 만들 수 있는 수들을 의미합니다.
소인수분해(Prime Factorisation)는 주어진 수를 소인수들로 반복해서 나누어 해당 수의 모든 소인수를 찾아내는 과정입니다.
예시 : N = 120 소인수 = 2 5 3 인수분해 : 2 * 2 * 2 * 3 * 5
소인수의 핵심 특징
- 어떤 수의 소인수 집합은 항상 유일합니다.
- 소인수분해는 배수 관계 판별, 공통 분모 찾기 등 다양한 수학적 계산에서 널리 활용됩니다.
- 암호학 분야에서도 매우 중요한 핵심 개념입니다.
이제 C++을 이용해 숫자의 소인수를 구하는 프로그램을 살펴보겠습니다.
예제 코드
#include <iostream>
#include <math.h>
using namespace std;
void printPrimeFactors(int n) {
while (n%2 == 0){
cout<<"2\t";
n = n/2;
}
for (int i = 3; i <= sqrt(n); i = i+2){
while (n%i == 0){
cout<<i<<"\t";
n = n/i;
}
}
if (n > 2)
cout<<n<<"\t";
}
int main() {
int n = 2632;
cout<<"Prime factors of "<<n<<" are :\t";
printPrimeFactors(n);
return 0;
}
알고리즘 동작 원리
위 코드의 로직은 다음 세 단계로 구성됩니다.
- 1단계: 수가 짝수인 동안 2로 계속 나누면서 2를 출력합니다. 이렇게 하면 모든 2의 인수가 제거됩니다.
- 2단계: 3부터 √n까지 홀수만 검사하며, 나누어 떨어지면 해당 수를 출력하고 n을 그 값으로 나눕니다. √n까지만 검사해도 되는 이유는 n의 인수 쌍 중 하나는 반드시 √n 이하이기 때문입니다.
- 3단계: 위 과정이 끝난 후 n이 2보다 크면 남은 n 자체가 소수이므로 마지막 소인수로 출력합니다.
이 알고리즘의 시간 복잡도는 O(√n)으로, 효율적으로 소인수를 찾을 수 있습니다.
실행 결과
Prime factors of 2632 are :2 2 2 7 47