[백준] 11653 : 소인수분해 JAVA 풀이

소인수분해란 1보다 큰 자연수를 소수들만의 곱으로 나타내는 것이다.

입력받은 수가 소수로 나눠떨어질 때마다 그 소수를 출력해주면 되는데, 

처음엔 2부터 입력받은 수 사이의 소수를 다 구한다음 그 소수로 나눠봐야 하나??싶었다.

하지만 좀 더 고민해보니 그럴 필요가 없다는 걸 알게 됐다.

 

소수가 아닌 수는 합성수인데, 합성수는 둘 이상의 소수를 곱한 수이므로 소수들로 쪼갤 수 있다.

그러니 2부터(1은 소수가 아니니 제외) 입력받은 수까지 1씩 증가시켜나가면서 입력받은 수를 나누다보면

자연스럽게 소수들로 쪼개지는 것이다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        for(int i=2;i<=N;i++){
            while(N%i==0){
                    System.out.println(i);
                    N /= i;
            }
        }
    }
    
}