JAVA백준 문제풀이 (10) 11653: 소인수분해

 

 

이 문제를 보고 내가 생각한 풀이 방식은 에라토스테네스의 체를 이용해 소수의 배열을 먼저 구한 뒤 그것으로 나누는 것이였는데..

그러면 바로 시간 제한에 걸려서 탈락한다.

생각해보면 애초에 그런 식으로 풀어야 할 이유가 없다.

그냥 소수인 2부터 나누기 시작해서 2로 나눈 나머지가 0이 아니라면 나누는 수를 1씩 더하면 된다.

 

 

" 엥?? 소인수 분해는 소수로만 나눠야 하는데요?? " 

 

 

생각해보자.

어차피 2로 나눌 수 없는 수는 4로 나눌 수 없고 3으로 나눌 수 없는 수는 6으로 나눌 수 없다.

띠용~

작은 수부터 점점 키워나가면 무조건 소수로 나눠지게 된다.

 

 

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 inputNum = Integer.parseInt(br.readLine());
        int primeNum = 2;

        while ( inputNum != 1 ) {
            if ( inputNum % primeNum == 0 ) {
                inputNum /= primeNum;
                System.out.println(primeNum);
            } else {
                primeNum++;
            }
        }
    }
}

 

 

시간 제한 초과로 여러 번 틀리는 바람에 노이로제에 걸려 BufferdReader를 사용했지만 Scanner로도 충분할 것 같다.