백준 18384 자바 - PRIM (BOJ 18384 JAVA)

문제 : boj18384

 

 

  이 문제를 풀기 위해 코드적으로 알아야 하는 것은 다음의 두가지 이다.

 

1. 1000000보다 처음으로 큰 소수까지의 모든 소수

2. 특정 입력에 대해 빠르게 그보다 작지않은 소수를 구하기

 

  '1'의 경우 에라토스테네스의 체로 구할 수 있다. 참고로 1000000보다 처음으로 큰 소수는 1000003이다. 이건 정확히 몰라도 된다. 대충 1000100 까지 구하면 된다. 참고로 n이하의 모든 소수를 알기위해 에라토스테네스의 체를 사용할 때는 sqrt(n) 까지만 확인하면 된다. 이것에 대한 설명 및 증명은 이 글('에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유')에 있다.

 

  '2'의 경우 이분탐색을 활용하면 된다. c++의 upper_bound에 해당하는걸 사용하면 더 쉽게 구할 수 있다. 자바의 경우 BinarySearch를 사용해서도 가능은하지만, TreeSet을 사용하는 것이 더 편하게 구현할 수 있다.

 

  정리하자면

A. 에라토스테네스의 체로 1000003까지의 모든 소수를 구해서 TreeSet에 담는다.

B. 각 테스트 케이스에 주어진 모든 수에 대해 TreeSet에서 ceiling을 확인한다(c++의 upper_bound와 동일한 역할로, ceiling(n) 이라면 TreeSet에 들어있는 값들 중 최초로 n이상인 값을 O(logN)에 찾아준다.).

C. 찾은 값을 테스트케이스별로 더한다.

 

 

코드 : github

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

public class Main {
    private final static int MAX_NUM = 1000003;
    private TreeSet<Integer> findPn() {
        boolean[] pnChk = new boolean[MAX_NUM+1];
        for (int base = 3; base <= Math.sqrt(MAX_NUM); base+=2) {
            if (pnChk[base]) continue;
            int tmp = base+base;
            while (tmp <= MAX_NUM) {
                pnChk[tmp] = true;
                tmp+=base;
            }
        }

        TreeSet<Integer> pn = new TreeSet<>();
        pn.add(2);
        for (int i = 3; i <= MAX_NUM; i+=2) {
            if (!pnChk[i])
                pn.add(i);
        }
        return pn;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        TreeSet<Integer> pn = findPn();
        int t = Integer.parseInt(br.readLine());
        StringBuilder answer = new StringBuilder();
        while (t-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long sum = 0;
            while (st.hasMoreTokens()) {
                sum += pn.ceiling(Integer.parseInt(st.nextToken()));
            }
            answer.append(sum).append('\n');
        }
        System.out.print(answer);
    }


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