[백준 알고리즘] 4948 - 베르트랑 공준

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

4948번: 베르트랑 공준

 

문제는 위와 같으면 이 문제는 다른 소수 문제들과 마찬가지로 먼저 에라토스테네스의 체를 통해 123456 * 2 수까지의 소수를 구한 다음, 0이 입력될 때까지 반복문을 돌면서 (주어진 숫자 + 1)부터 (주어진 숫자 * 2)까지 수 중 소수가 있는지 확인하여 소수인 경우 개수를 증가시키고 이 개수를 나중에 출력하는 방식으로 해결할 수 있습니다.

 

자바 코드는 다음과 같습니다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 소수인 경우 true, 아닌 경우 false
        boolean[] primeNum = new boolean[(123456 * 2) + 1];
        Arrays.fill(primeNum, true);
        primeNum[0] = primeNum[1] = false;

        for (int i = 2; i * i < primeNum.length; i++) {
            for (int j = i * i; j < primeNum.length; j += i) {  // i를 제외한 i의 배수를 찾아 false로 변경
                primeNum[j] = false;
            }
        }

        StringBuilder sb = new StringBuilder();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            int n = Integer.parseInt(br.readLine());

            // 0인 경우 입력 종료
            if (n == 0) {
                break;
            }

            int count = 0;
            // n 보다 크고 2n 보다 작거나 같은 소수 찾아서 수 세기
            for (int i = n + 1; i < (n * 2) + 1; i++) {
                if (primeNum[i]) {
                    count++;
                }
            }

            sb.append(count).append("\n");
        }

        // 출력
        System.out.print(sb);
    }
}