[알고리즘] 소인수분해 - 백준

문제

11653번: 소인수분해

풀이 - Java 11

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

public class Q11653 {
    public static void main(String[] args) throws IOException {
        int n = input();
        output(n);
    }

    static int input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        return Integer.parseInt(br.readLine());
    }

    static void output(int n) {
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                System.out.println(i);
                n /= i;
            }
        }
        if (n > 1) System.out.println(n);
    }
}

소인수분해하는 프로그램을 작성하고 그 결과값을 반환하도록 알고리즘을 작성하여야 한다.

static void output(int n) {
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            System.out.println(i);
            n /= i;
        }
    }
    if (n > 1) System.out.println(n);
}

소인수란 주어진 자연수를 나누어 떨어뜨리는 약수 중에서 소수인 약수를 말한다.
문제에서 요구하는 것은 작은 소인수부터 나오도록 분해하는 것이다.
풀이한 방식은 먼저 가장 작은 소인수인 2부터 n의 제곱근까지 반복문을 진행하면서 해당 값으로 소인수분해가 가능할 때까지 분해하고 그 연산을 진행하는 것이다.

n의 제곱근까지만 반복문을 진행하는 이유는 가장 큰 소인수는 n의 제곱근까지이기 때문이다. 예를 들어 16이라는 수를 두 수의 곱으로 나타내면 다음과 같을 것이다.

이렇게 보면 두 수 모두가 16의 제곱근인 4를 넘길 수 없다. 따라서 주어진 수 n의 제곱근 이하의 숫자들만 확인하면 n의 모든 소인수를 확인할 수 있게된다.

이후 n을 반복문 안의 소인수 i로 나누어 떨어지지 않을때까지 소인수분해를 반복한다.

while (n % i == 0) {
    System.out.println(i);
    n /= i;
}

이후 마지막으로 n이 1보다 큰지 확인한다. 1보다 크다면 n은 마지막 소인수이다.

if (n > 1) System.out.println(n);