[Dev-Ping9] 백준 11653번 - 소인수분해 (Java)

 

# 문제설명

• 소수찾기 알고리즘을 구현해봤다면, 약수들의 중간값인 sqrt(n) 까지만 돌리면 된다는 것을 알고 있을 것이다.
• 그럼 구현만하면 끝

 

# 코드 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main{

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

        int n = Integer.parseInt(br.readLine());
        
        for(int i=2;i*i<=n; i++){ //n은 계속 유동적으로 바뀐다. 소수를 만나면 while문이 동작하지 않는다.
            while(n%i==0){
                n/=i;
                bw.write(i+"\n");
            }
        }
        if(n>1){ // 소수 
            bw.write(n+"\n");
        }
        
        bw.flush();
        bw.close();
        br.close();
    }
}