[백준][Java] 4948번 베르트랑 공준

안녕하세요 :)

적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.

혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자  글을 써 내려갑니다.

 

---

 

백준 4948 베르트랑 공준

이번 문제는 입력으로 주어진 n에 대해 (n, 2n) 범위의 소수 개수를 출력하는 문제입니다.

 

📘 문제

 

💡 해결 방법

먼저 입력된 수 n이 0이 아닐 때까지 반복해서 입력을 받고,

(n + 1)부터 2n까지의 수 중에서 소수인 수를 카운트합니다.

소수 판별은 2부터 √n까지 나눠보는 방식으로 처리합니다.

 

✅ 풀이 및 설명 (설명은 더보기 클릭)

 

• 입력은 여러 줄로 들어오기 때문에, while 루프를 통해 계속 입력을 받습니다.
• n == 0일 경우 입력이 끝났다는 의미이므로 종료합니다.
• 매 입력마다 (n, 2n] 범위 내의 수들 중 소수를 체크하고, 개수를 세어 StringBuilder에 담아둡니다.
• 마지막에 한 번에 출력해줍니다.

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder sb = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) break;

            int count = 0;
            for (int i = n + 1; i <= 2 * n; i++) {
                if (isPrime(i)) {
                    count++;
                }
            }
            sb.append(count).append("\n");
        }

        System.out.print(sb);
        br.close();
    }

    // 소수 판별 함수: 2부터 sqrt(num)까지 나눠서 소수 여부 체크
    private static boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

 

이 문제는 소수 판별의 기본적인 로직과 함께 반복 입력 처리에 익수해지기 좋은 문제였어요.

이후 비숫한 문제에서 속도를 높이기 위해 에라토스테네스의 체를 활용하는 방법도 익혀두면 좋을 것 같네요.

 

---

공부하면서 유용했던 부분 메모 겸 공유하고자 끄적입니다.

고쳐야 하는 부분 있다면 댓글 남겨주시면 수정하겠습니다.

행복한 하루 보내세요 (❁´◡`❁)