이번에 풀어본 문제는
백준 4948번 베르트랑 공준 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static boolean [] notPrime;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Integer> inputs = new ArrayList<>();
        int maxValue = Integer.MIN_VALUE;

        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n < 1) break;
            //입력값 중 최댓값
            maxValue = Math.max(maxValue, n);
            inputs.add(n);
        }
        notPrime = new boolean[(maxValue * 2) + 1];
        getPrime(notPrime.length);

        int[] primeCount = new int[notPrime.length];
        for (int i = 1; i < primeCount.length; i++) {
            // 소수가 아니면 그대로, 맞으면 + 1
            primeCount[i] = notPrime[i] ? primeCount[i - 1] : primeCount[i - 1] + 1;
        }

        StringBuilder sb = new StringBuilder();
        for (int start : inputs) {
            int end = start * 2;
            sb.append(primeCount[end] - primeCount[start]).append("\n");
        }
        System.out.print(sb);
    }
    static void getPrime(int size) {
        for (int i = 2; i * i < size; i++) {
            if (!notPrime[i]) {
                for (int j = i * i; j < size; j += i) {
                    notPrime[j] = true;
                }
            }
        }
    }
}

📝 풀이

입력에 N값이 주어졌을 때, N부터 2N까지의 숫자 사이에 소수가 몇개 존재하는지 출력하는 문제입니다.
에라토스테네스의 체를 활용해 모든 소수를 구해놓고, primeCount배열에 각 인덱스 까지의 소수 개수를 담아놓은 후, 입력값을 담아둔 리스트를 탐색하며 인덱스 끼리의 차이를 StringBuilder에 넣어 출력값을 만들어 주면 해결할 수 있습니다.

📜 후기

요즘 문제를 많이 못풀어서 감을 잃었었는데, 억지로 골드 문제를 풀다가 자신감을 잃는 것 보다 조금 쉬운 난이도의 문제를 풀며 감을 다시 찾아야할 것 같습니다. 이번 주는 실버 1~2 문제만 해결해 볼 생각이에요!