[백준] 11653 소인수분해 (Java)

[11653 소인수분해]

난이도: 실버5

11653번: 소인수분해

문제

 

입력

출력

---

[아이디어]

처음에는 나누는 수가 소수인지 판단해주는 방식을 사용하였다. 그런데 계속 시간 초과가 떴다.

왜 그럴까 생각해보니 이미 소수이면 해당 수로 다 나누기 때문에 그의 배수로는 나눌 수 없다.

예를 들면 12 = 2 x 2 x 3 이다. 이 때, 12 % 2 == 0 이므로 12 / 2 = 6 / 2 = 3 을 만들어버린다.

따라서 이후에 4, 6, 8 등으로는 나눌 수 없게 된다.

물론 그 전에 수가 1이 된다면 반복문을 빠져나온다.

---

[JAVA 코드]

import java.io.*;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	
	static int N;

	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine());
		if(N == 1) return;
		
		for(int i = 2; i <= N; i++) {
			if(N % i == 0) {
				while(N % i == 0) {
					output.append(i + "\n");
					N /= i;
				}
			}
			if(N == 1) break;
		}
		System.out.println(output);
	}

}