11653.소인수분해

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

## 입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

## 출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	99599	54229	42046	53.083%

https://www.acmicpc.net/problem/11653

풀이

로직을 보면 아래와 같이 풀이될수있다.

72 / 2 = 36;
36 / 2 = 18;
18 / 2 = 9;
9 / 3 = 3;
3 / 3= 1;
1 < 2; (break);

72를 나눈다고 했을때 나눠지는 값으로 계속해서 나눈다.

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.LinkedList;  
import java.util.List;  

public class 소인수분해 {  

    public static void main(String[] args) throws IOException {  
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));  

        int n = Integer.parseInt(br.readLine());  

        List<Integer> list = new LinkedList<>();  

        while (true){  
            if(n < 2) break;  //n이 2보다 작을때 while문 탈출

            for(int i=2; i<=n; i++){  
                if(n%i == 0){  //n이 i로 나눠질때
                    list.add(i);  //나눠지는 값은 소수이므로, list에 넣어준다.
                    n /= i;  //n을 i로 나누고 for문을 탈출한다.
                    break;  
                }  
            }  
        }  
        list.forEach(System.out::println);  
        br.close();  
    }  
}