11653 소인수분해 (Java)

11653 소인수분해 (Java)

https://www.acmicpc.net/problem/11653

정수 N이 정해지면, 소인수분해하면 됩니다.
간단한 문제이지만, Java로 풀어야해서 블로그 글을 참조했습니다.

1. 나눌 수를 2부터 시작해서 정수 N을 나눈 나머지가 0이 될때까지 나누면 됩니다.
2. 해당 조건이 완료되었다면, N이 1이 아닐경우 출력해주면 됩니다.

*왜 해당 코드를 써야할지 의문이 들수 있습니다. *
예를 들어 더이상 나누어지지 않는 17의 경우 2를 나누었을때도 0 이아니므로 while문이 종료됩니다.
이렇게 되면 출력을 하지 않고 끝나기 때문에 밑에 N이 1이 아닌경우 출력을 하게끔 만들어줘야합니다. N이 1이라면 소인수로 깔끔히 분해된 상태겠지요.

또다른 의문점이 들 수 있습니다.
i는 무조건 1씩 올라가는데 소인수만 분해를 하는가? 4나 6으로도 분해될 수 있는거 아닌가? 입니다. (저는 이게 좀 헷갈렸습니다.)
→ 그러나 이미 앞에서 2와 3으로 나누는 과정을 거치며 4나 6으로 나눌 상황을 배제하게됩니다. 그러므로 자동으로 소인수분해를 할 수 있게 됩니다.

자바에서는 Scanner를 통해 인풋을 받습니다. 또한 Systehttp://m.out.prinln으로 출력을 할 수 있습니다.

import java.util.Scanner;

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

        int N = in.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);
        }
    }
}