[백준] 3896번. 소수 사이 수열(JAVA)

문제

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

---

풀이(17분)

import java.io.*;
import java.util.*;

public class Main {

    // 소수의 리스트를 먼저 구해두자.
    // 만약 소수의 리스트에 포함되어 있다면 -> 0을 바로 출력한다.
    // 포함되어있지 않다면, 자기보다 큰 첫번째의 소수값과 인덱스를 찾는다.
    // 23과 29 사이에 예를 들어, 27이 k였다면 양쪽으로 4 + 2를 구하면 된다.(27 - 23) + (29 - 27)
    // 10의 경우 3 + 1 -> (10 - 7) + (11 - 7)
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Integer> primeList = primeFinder();

        for(int i = 0; i < n; i++){
            int testCase = Integer.parseInt(br.readLine());
            if(primeList.contains(testCase)){
                System.out.println(0);
                continue;
            }
            int answer = 0;
            int start = 0;
            int end = primeList.size() - 1;
            while(start <= end){
                int mid = (start + end) / 2;
                if(primeList.get(mid) > testCase){
                    end = mid - 1;
                    continue;
                }
                start = mid + 1;
            }
            answer += primeList.get(start) - primeList.get(start - 1);
            System.out.println(answer);
        }

    }

    public static List<Integer> primeFinder(){
        int max = 1_299_709;
        List<Integer> list = new ArrayList<>();
        boolean[] isPrime = new boolean[max+1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for(long i = 2; i <= max; i++){
            if(isPrime[(int)i]){
                list.add((int)i);
                for(long j = i * i; j <= max; j += i){
                    isPrime[(int)j] = false;
                }
            }
        }
        return list;
    }
}

---

문제 풀이 전략

 

소수의 리스트를 먼저 구해야 했다.

이때, 에라토스테네스의 체를 사용하였는데 이 경우 max값이 1,299,709까지이기 때문에 반복문의 타입을 long으로 하고 인덱스를 int로 다운캐스팅 해주자.

 

소수의 리스트를 모두 구했다면 해야 할 것은 다음과 같다.

1. 소수인지 판별한다.

-> 소수라면

리스트에 들어있는 값이라면 소수이고, 이 경우 소수 사이의 길이가 존재할 수 없으므로 0을 출력하고 끝낸다.

-> 소수가 아니라면

2. 이분탐색으로 자기보다 큰 최소의 소수를 찾는다.

3. 이후 자기보다 작은 최대의 소수를 찾아 두 수를 뺀 값이 길이가 된다.