소인수분해란?

자연수를 소수의 곱으로 나타내는 것을 소인수분해라고한다.
예를 들자면, 12는 2 x 2 x 3의 소수로 분해된다.

그럼 코드를 사용한 소인수분해를 구현하는 방법을 알아보자!

---

N을 모든 숫자와 나누기

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++;
	}
}

1. num을 k로 나누고 나머지가 0이라면 몫을 다시 k로 나눈다.

2. 1번을 반복한다.

3. 더 이상 나누어 떨어지지 않는다면 k를 1로 증가시킨다.

4. 다시 1번 부터 3번을 반복한다.

5. 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이 나오게 된다.