자연수를 소수의 곱으로 나타내는 것을 소인수분해라고한다.
예를 들자면, 12는 2 x 2 x 3의 소수로 분해된다.
그럼 코드를 사용한 소인수분해를 구현하는 방법을 알아보자!
N을 2부터 나누는데, 이때 N이 나누어 떨어지면 나누는 숫자는 N의 인수가 된다. 코드로 살펴 보자
int k = 2;
int num = 12; // 임시로 값을 12로 설정.
while (num != 1) {
if (num % k == 0) {
System.out.println(k + " ");
num /= k;
} else {
k++;
}
}
num
을 k
로 나누고 나머지가 0이라면 몫을 다시 k
로 나눈다.
1번을 반복한다.
더 이상 나누어 떨어지지 않는다면 k
를 1로 증가시킨다.
다시 1번 부터 3번을 반복한다.
num
이 1이 되는 순간 while
문을 종료한다.
12로 예를 들어 보자
1. k = 2 일 때
12 / 2 = 몫: 6, 나머지: 0
6 / 2 = 몫: 3, 나머지: 0
3 / 2 = 몫: 1, 나머지: 1
나머지가 1이라면 k를 증가 시킨다.
2. k = 3 일 때
3 / 3 = 몫: 1, 나머지: 0
몫이 1이라면 반복문 종료
위의 값을 정리하면 2 2 3이 나오게 된다.