[Java] 소인수분해

1. 문제 설명

자연수를 소인수 분해한 결과를 출력하는 프로그램을 작성해보자

입력 형식

첫 줄에는 테스트케이스의 수 T가 주어진다. T는 1이상 100이하의 자연수이다.

각 테스트케이스는 한 줄로 구성되며 소인수 분해를 할 자연수가 주어진다. 이 자연수는 2이상 10억이하이다.

출력 형식

각 테스트케이스에 대한 정답을 두 줄씩 출력한다.

테스트케이스의 첫 줄에는 테스트케이스의 번호를 #%d: 와 같은 형식으로 출력한다.
두 번째 줄에는 입력으로 주어진 숫자들의 소인수들을 공백으로 구분하여 오름차순으로 출력한다. 여러 번 곱해진 소인수는 그 횟수 만큼 출력한다.

2. 알고리즘 접근

소인수 분해

1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것

만약 소수인 약수로 몫이 소수가 될 때까지 계속 나누는 풀이를 한다면 O(N)이 된다
허나 입력 형식에 자연수는 10억 이하이므로 위 방식의 풀이가 아닌 개선된 풀이 사용

소인수 분해의 결과는 소수가 됨이 자명하다
그러므로 [2, $\sqrt n$]의 범위 에서 약수를 찾지못하면 소수이므로 소인수분해 x

3. 소스코드

import java.util.ArrayList;
import java.util.Scanner;

public class Q4E {
    public static Scanner sc = new Scanner(System.in);
    private static void testCase(int caseIndex) {
        long N = sc.nextInt(); // 소인수 분해 할 자연수

        ArrayList<Long> factors = MathU.factorize(N);

        System.out.printf("#%d:\n", caseIndex);

        for(long fac : factors){
            System.out.print(fac + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int caseSize = sc.nextInt(); // 테스트케이스 수 입력

        for(int caseIndex = 1; caseIndex <= caseSize; caseIndex++){
            testCase(caseIndex);
        }
    }
}
class MathU{

    public static ArrayList<Long> factorize(long n) {
        ArrayList<Long> factors = new ArrayList<>();

        for(long div = 2; div * div <= n; div++){
            while (n % div == 0){
                // 소인수 목록에 div 추가
                factors.add(div);

                // N에서 소인수만큼 나눈다
                n /= div;
            }
        }
        if(n > 1){
            // 소인수를 찾지못하고 남아있는 n이라면 반드시 소수다 이를 소인수에 추가
            factors.add(n);
        }

        return factors;

    }
}