소인수분해 (Prime Factorization)

참고

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4

소인수분해 - 위키백과, 우리 모두의 백과사전

정의

• 정수 N을 소수의 곱으로 분해

방법

• N을 소인수분해 할 때, 가장 큰 값이 되는 경우는 루트 N이다.
• 2부터 루트 N까지 N을 나눌 수 없을 때까지 계속 나눈다.

for (int i=2; i*i <= input; i++) {
    while (input%i == 0) {
        System.out.printf("%d\n", i);
        input /= i;
    }
}

if (input > 1) {
    System.out.printf("%d\n", input);
}