[백준/Java] 11653번 :: 소인수분해

| 문제

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

 

| 입력

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

 

| 출력

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

 

| 예제 입력

72

 

| 예제 출력

2
2
2
3
3

 

| 풀이

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


public class Main
{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i=2; i<=N; i++)
			while( N%i == 0)
			{
				System.out.println(i);
				N /= i;
			}
			
	}
}

 

| 정리

문제 풀이 과정은 너무 쉬웠다. 근데 N까지 반복문을 돌리는게 너무 비효율적이라고 생각해서 찾아봤더니

제곱근을 활용해서 풀이를 하신 분들도 많은 것 같다.

그 방법은 어떻게 해서 나오게 된 풀이법인지 공부해봐야겠음!!