문제

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

입력

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

출력

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

풀이

소수 찾는 방법과 같이 2부터 시작해서 나누어 떨어지는 것이 있는지 확인하면 된다. 또한 주어진 수의 제곱근까지만 구하면 된다. 왜냐하면 어떤 N이 두 개이상 곱으로 나타낼 수 있을 때 인수 중 한 개 이상은 반드시 √N보다 작거나 같기 때문이다. 이후 for문이 끝나면 남은 인수 하나가 존재하기때문에 그 역시 출력해주어야 한다.

소스

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		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);
		}

	}

}