백준 11653 - 소인수 분해

Java

11653 번 - 소인수 분해

문제

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

접근 방법

가장 작은 소수는 2이므로, 2부터 최대 수 MAX인 10000000까지 증가시킨다.
주어진 수와 나누어 나머지가 0이면, 나누어 떨어지는 것이므로 그 수로 최대한 나누며 출력한다.
만약 주어진 수가 1이 되면 반복을 종료한다.

코드

/*
11653번 - 소인수분해
https://www.acmicpc.net/problem/11653
*/

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

public class Main {
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int MAX = 10000000;
    	int n = Integer.parseInt(br.readLine());
    	for(int i = 2; i < MAX; i++) {
    		if(n % i == 0) {		// 만약 나누어 떨어지면
    			while(true) {		// 그 수로 최대한 나눈다.
    				if(n % i == 0) {
    					n /= i;
    					System.out.println(i);
    				}
    				else {
    					break;
    				}
    			}
    			if(n == 1)			// 주어진 수가 1이되면 종료
    				break;
    		}
    	}
    	br.close();
    }
}

총평

난이도

⭐★★★★

후기

처음에는 모든 소수를 구하고 난 뒤 구한 소수로 하나씩 나누어 볼려 하였는데, 오히려 이 방법이 더 비효율적인 것 같아 완전 탐색으로 해결하였다.
다음에 소수를 구할 경우가 있으면 소수 구하기을 참고한다.

개선할 점

없