백준 11653 소인수분해 자바

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

 

문제

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

 

입력

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

 

출력

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

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());

        getPrimeFactorization(num);
    }

    private static void getPrimeFactorization(int num) {
        if (num > 1) {
            List<Integer> primes = new ArrayList<>();
            primes.add(2);

            // 소수 구하기
            for (int i = 3; i <= num; i+=2) {
                boolean isPrime = true;
                for (Integer prime : primes) {
                    if (i % prime == 0) {
                        isPrime = false;
                        break;
                    }
                }

                if (isPrime) {
                    primes.add(i);
                }
            }

            // 소인수분해 하기
            for (Integer prime : primes) {
                while (num != 0) {
                    if (num % prime == 0) {
                        num /= prime;
                        System.out.println(prime);
                    } else {
                        break;
                    }
                }
            }
        }
    }
}

 

풀이

내가 처음으로 푼 방법은 일단 입력 받은 num까지 소수를 모두 구해 리스트에 넣어놓고, 이 리스트의 수를 처음부터 반복하면서 num에서 나눠가는 방식이었다. 근데 이렇게 제출하면 시간 초과가 발생한다.

문제에서 입력값이 10,000,000까지 발생할 수 있다고 했는데, 따져보니 복잡도가 O(n²)라서 천만 단위에서는 통과 불가능한 구조다.

 

복잡도

• 소수 생성 O(n√n)
• 소인수분해 O(n)
• 총 O(n²)

 

개선점

챗지피티에게 계산 시간을 개선할 수 있는 방법을 물어봤다. 병목 지점은 소수를 생성하는 부분이었는데, 모든 홀수에 대해 소수인지를 판단할 필요 없고 2부터 √n까지만 나눠도 된다는 것이었다. 즉, 소수를 판단해서 구할 필요가 없다는 것이었다.

• as-is : 2는 미리 넣어놓고, 3부터 n(목표값)까지 홀수에 대해 판단
• to-be : 2부터 √n까지, 판단하지 않음

 

왜 √n까지만 판단하면 되는가
√n까지만 검사해도 모든 약수를 한번씩 다 검사할 수 있다.
예) √72보다 작은 수로 나누면, 짝이 되는 약수는 √72보다 크다.

약수 쌍	곱
1 X 72	= 72
2 X 36	= 72
3 X 24	= 72
4 X 18	= 72
6 X 12	= 72
8.48 × 8.48	= 72 (√72 ≈ 8.48)

 

최종 코드

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 num = Integer.parseInt(br.readLine());

        if (num > 1) {
            getPrimeFactorization(num);
        }
    }

    private static void getPrimeFactorization(int num) {
        for (int i = 2; i * i <= num; i++) {
            while (num % i == 0) {
                System.out.println(i);
                num /= i;
            }
        }

        // 마지막으로 남은 수 고려
        if  (num > 1) {
            System.out.println(num);
        }
    }
}

 

결과