[JAVA] 백준 11653. 소인수분해

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제
입력
출력
요약
풀이과정
나의 코드
시간 비교

문제

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

입력

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

출력

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

요약

단순히 주어지는 수를 소인수분해하는 문제이다.

풀이과정

일단 N이 1인지 확인 후, 1인 경우에는 아무것도 출력하지 않고 그냥 프로그램을 종료시킨다.

이후 가장 작은 소수인 2부터 N에 나눠보고, 만약 나누어 떨어지면 더이상 나누어떨어지지 않을 때 까지 그 수로 나누다가, 수를 1증가 시키고… 이런 흐름이다.

그렇다면 2부터 시작해서 N까지 다 나눠보면 될까? 그래도 상관은 없지만 이런 정리가 있다.

모든 합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다.

즉, 어떤 수의 약수를 구할 때 그 수의 제곱근보다 큰 수는 나눠보지 않아도 된다는 뜻이다.
증명은 아래와 같다

\(n\)을 합성수라 하자. 그러면 \(n=ab, 1<a,b<n\)이다. 만약 \(a, b\)가 둘 다 \(\sqrt n\)보다 크다면, \(n=\sqrt n\sqrt n<ab=n\)이 되어 모순이다. 따라서 \(a, b\)중 적어도 하나는 \(\sqrt n\)보다 같거나 작다.

나의 코드

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());
        
        if(N != 1){  // N이 1이 아닐때만 실행
            for(int i=2; i<=Math.sqrt(N); i++){  // 2부터 N의 제곱근 이하까지 나눠봄
                while(N%i == 0){  // 현재 숫자로 나누어떨어질 때까지 나눔
                    System.out.println(i);  // 나누어 떨어질 때마다 숫자 출력
                    N /= i;  // N에 실제로 나눔
                }
            }
            
            if(N != 1){  // 아래서 설명
                System.out.println(N);
            }
        }
    }
}

1로 나누는 것은 의미가 없으므로 2부터 N에 나눠본다. 만약 N에 i가 나누어 떨어지면 해당 숫자를 출력하고, 실제로 N에다가 나눈다.

while문은 조건이 참일동안 반복하므로, 계속 N에 i를 나누다가 더이상 나누어 떨어지지 않으면 반복을 종료하고 for문에서 i++;후 다음 숫자를 진행한다.

그럼 마지막은 무슨 부분일까? 계속 나누면 결국 N이 1이 되어 더이상 나눌 수 없게 되며, 이 때까지 출력된 숫자가 소인수분해의 결과다.

그러나 예제 입력에도 있는 9991 같은 경우는? 97로 나눈면 103이 되는데, for문 조건에서 제곱근 이하까지만 반복한다. 9991의 제곱근은 대략 99이므로 103으로 나누지 않아서 출력이 안된다.
그렇기 때문에 마지막에 N이 1이 아닌지 확인해서 아니면 그 N을 출력해주는 것이다.

이는 제곱근 이하 까지만 for 루프를 돌려서 생기는 문제이므로, 만약 for문의 조건을 i<=N으로 할것이라면 이 부분은 필요없다.