소인수분해의 개념과 간단한 풀이법

개념

어떤 자연수를 소수의 곱으로 나타내는 것을 소인수분해라고 한다. 예를 들어, 12를 소인수분해하면 2 x 2 x 3으로 나타낼 수 있, 이때 2와 3은 소수이다.

소인수분해에 대한 정리

• 배수 판정법
• 모든 합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다.

알고리즘

1. 소수 2부터 시작하여 입력받은 수를 나누어 떨어지는지(n%i == 0) 확인합니다.
2. 만약 나누어 떨어진다면, 그 수를 소인수로 등록하고 해당 수로 나눈 값을 저장한다.
3. 다시 나눈 수부터 나누어 떨어지는지 확인하는 과정을 1이 될 때까지 반복한다.

*작은 소수에서 n%i == 0이 성립하지 못한다면 그보다 큰 합성수는 n%i == 0이 성립하지 못하므로 작은 수부터 시작했을 때 나누어 떨어지는 수가 소수라는 점을 이용한다.

while (N > 1) {
    for (int i = 2;;) {
        if (N == 1) return;

        if (N % i == 0) {
            System.out.println(i);
            N /= i;
        } else {
            i++;
        }
    }
}

참고 자료

나무위키 - 소인수분해