[BOJ/Step9] 11653 : 소인수분해 (JAVA)

www.acmicpc.net/problem/11653

11653번: 소인수분해

---

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

72

 

예제 출력 1

2

2

2

3

3

 

예제 입력 2

3

 

예제 출력 2

3

 

예제 입력 3

6

 

예제 출력 3

2

3

 

예제 입력 4

2

 

예제 출력 4

2

 

예제 입력 5

9991

 

예제 출력 5

97

103

---

풀이

(경험담 : 전과 같이 미리 소수를 구해 배열에 넣어두려고 하면 완전 망한다...)

1. 입력받은 n을 a로 나눠서 나머지가 0일때 a를 버퍼로 출력하고, n을 a로 나눠준다. a는 2부터

2. n이 더이상 a로 나눠지지 않으면 a++

3. n이 1일때 반복문을 종료하고 버퍼를 출력

 

import java.io.*;
import java.util.Scanner;

public class B11653 {

	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());
		int a = 2;	
		
		while(n != 1) {
			if(n % a == 0) {
				n /= a;
				bw.write(a + "\n");
			} else {
				a++;
			}
		}
		bw.flush();
	}
}