[자바] 백준 16563 - 어려운 소인수분해 (java)

목차

문제 : boj16563

 

 

필요 알고리즘

• 정수론, 소수 판정, 에라토스테네스의 체
  
  • 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  백준 3142를 풀면서 좀 더 개선된 소인수분해 테크닉을 익히게 되어, 민상님의 소개로(?) 풀어본 관련 문제이다. 코드 1은 기존에 내가 쓰던방식으로 푼 코드이고, 코드 2가 개선된 소인수분해 테크닉으로 짜본 코드이다. 코드 1이 3배정도 오래걸린다.

 

  '에라토스테네스의 체를 활용한 소인수분해' 글을 쓰면서 이 문제를 기준으로 작성했으므로, 저 글에 풀이가 있다.

 

 

코드 1 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private List<Integer> getPn(int limit) {
        List<Integer> pn = new ArrayList<>();
        boolean[] isPn = new boolean[limit+1];
        int sqrtN = (int)Math.sqrt(limit);
        for (int i = 3; i <= sqrtN; i+=2) {
            if (isPn[i]) continue;
            int base = i+i;
            while (base <= limit) {
                isPn[base] = true;
                base+=i;
            }
        }
        pn.add(2);
        for (int i = 3; i <= limit; i+=2) {
            if (!isPn[i]) pn.add(i);
        }
        return pn;
    }

    public void solution() throws Exception {
        List<Integer> pn = getPn(5000000);
        Set<Integer> set = new HashSet<>(pn);

        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        while (n-->0) {
            int cur = Integer.parseInt(st.nextToken());

            int idx = 0;
            int curPn = pn.get(idx);
            while (curPn <= Math.sqrt(cur)) {
                while (cur % curPn == 0) {
                    cur /= curPn;
                    sb.append(curPn).append(' ');
                }
                curPn = pn.get(++idx);
            }
            if (set.contains(cur)) {
                sb.append(cur);
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

 

 

코드 2 (개선된 방식) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private int[] getMinimumPn(int limit) {
        int[] arr = new int[limit+1];
        for (int i = 2; i <= limit; i++) {
            if (arr[i] != 0) continue;

            int base = i;
            while(base <= limit) {
                if (arr[base] == 0)
                    arr[base] = i;
                base += i;
            }
        }
        return arr;
    }

    public void solution() throws Exception {
        int[] minimumPn = getMinimumPn(5000000);

        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        while (n-->0) {
            int cur = Integer.parseInt(st.nextToken());
            while (cur!=1) {
                sb.append(minimumPn[cur]).append(' ');
                cur /= minimumPn[cur];
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}