[Java] 소인수분해

소인수분해란?

소인수분해는 어떤 수를 소수인 인수로 분해하는 것이다. 소수는 1과 자기 자신으로만 나누어 떨어지는 정수를 의미한다.
코딩테스트 문제에서 자주 접하게 되어서 정리하게 되었다.

문제

정수 n 이 주어졌을때 소인수를 한 줄에 하나씩 출력한다.

int n = 420;
    @Test
    public void test() {
        for (int i = 2; i <= n; i++) {
            while(n % i ==0){
                System.out.println(i);
                n = n/i;
            }
        }
    }

출력

2
2
3
5
7

풀이

• 1은 인수가 아니므로 i=2 부터 시작한다.
• n 을 i 로 나눈 나머지가 0일때, i 가 n 의 인수이므로 한줄을 출력한다.
• n 을 i 로 나눈 몫으로 새로 할당을 해주어야 다음 인수를 찾을 수 있다.

참고
알고리즘 소인수분해 - Java 풀이
[Java]소인수분해