[알고리즘] 백준 11653번 소인수분해 :: 우유

---

소수 구하는 방법처럼 제곱근까지만 for문을 돌렸다.

소인수분해로 나누어지는 정수는 2부터 시작이고 2가 제일 작은 숫자기때문에

주어진 숫자는 제곱근 숫자 이하의 인수 개수만 가지기 때문 

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

public class Main {

	static int N;

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

		N = Integer.parseInt(br.readLine());

		for (int i = 2; i <= Math.sqrt(N); i++) {
			while (N % i == 0) {
				System.out.println(i);
				N /= i;
			}
		}

		if (N != 1)
			System.out.println(N);
	}
}