백준 9753 자바 - 짝 곱 (BOJ 9753 JAVA)

문제 : boj9753

 

 

  100000일 때 100001이 답이란걸 문제 예시에서 보여줬으므로 사실 100000이하의 소수 곱에 대해서만 신경쓰면 된다. 그리고 어차피 가장 작은 소수가 2 이므로 50000까지만 보면 된다. 따라서 5만 이하의 모든 소수를 우선 에라토스테네서의 체로 구한다.

 

  그리고 소수의 곱을 모든 쌍을 보면서 모두 구한다. 이 때 10만이 넘어간다면 제외해도 된다. 구한 값은 어차피 10만까지만 알면 되므로 배열에 넣어도 되고, 내 경우엔 더 큰 수를 빨리 구해보려고 TreeSet에 넣었다.

 

  이후 하나씩 입력받으면서 TreeSet의 ceiling을 출력하면 된다. '2'의 과정을 배열에 했다면 입력받은 값 이상을 순회하며 가장 작은 소수를 출력하면 된다.

 

 

 

코드 : github

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

public class Main {
    private static final int MAX = 51111;
    TreeSet<Integer> pnMult;

    private void initPrimeNum() {
        pnMult = new TreeSet<>();
        ArrayList<Integer> pn = new ArrayList<>();
        pn.add(2);

        boolean[] arr = new boolean[MAX+1];
        int sqrtMax = (int) Math.sqrt(MAX);

        for (int base = 3; base <= sqrtMax; base+=2) {
            if (arr[base]) continue;
            int tmp = base+base;

            while (tmp <= MAX) {
                arr[tmp] = true;
                tmp += base;
            }
        }

        for (int i = 3; i <= MAX; i+=2) {
            if (!arr[i])
                pn.add(i);
        }

        for (int i = 0; i < pn.size()-1; i++) {
            for (int j = i+1; j < pn.size(); j++) {
                int mult = pn.get(i) * pn.get(j);
                if (mult >= 100000) break;
                pnMult.add(mult);
            }
        }
        pnMult.add(100001);
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        initPrimeNum();
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            sb.append(pnMult.ceiling(Integer.parseInt(br.readLine()))).append('\n');
        }
        System.out.print(sb);
    }

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