[Java] 백준(실버-3) 4948번 - 베르트랑 공준

입출력 예시

Input

1
10
13
100
1000
10000
100000
0

Output

1
4
3
21
135
1033
8392

문제 풀이

---

먼저 베르트랑 공준이 무엇인지 궁금하여 찾아보았다.

베르트랑 공준이란?
2 이상의 임의의 정수 n에 대해서 아래 식을 만족하는 소수 p는 항상 존재한다.

n < p < 2n

문제에서는 베르트랑 공준 내용과 같이 n보다 크고 2n보다 작은 소수의 개수를 요구하고 있다.

이전에 풀었던 소수나 소수의 개수를 구하는 문제와 같이 에라토스테네스의 체를 이용하여 소수의 개수를 구하려고 한다.

생각해낸 아이디어는 다음과 같다.

• n이 0으로 입력될 때까지 n을 입력받는다.
• boolean 배열에 2부터 n*2 까지 순회하면서 소수인 경우는 false, 소수가 아닐 때는 true로 마킹한다.
• n부터 n*2까지 반복하며 false의 개수 즉, 소수의 개수를 찾는다.

아이디어를 코드로 작성해보자.

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

먼저 while문을 돌면서 n이 0으로 입력될 때까지 n을 입력받는다.

boolean[] prime_arr = new boolean[n*2+1];
prime_arr[0] = prime_arr[1] = true;

for(int i=2; i<=Math.sqrt(n*2); i++) {
    for(int j=i+i; j<prime_arr.length; j+=i) {
        prime_arr[j] = true;
    }
}

int cnt = 0;
for(int i=n+1; i<prime_arr.length; i++) {
    if(prime_arr[i] == false) cnt++;
}
bw.write(cnt+"\n");

n2+1 만큼 boolean 배열을 초기화하고, 소수가 아닌 0과 1 자리를 true로 마킹한다.
그리고 2부터 n2의 제곱근까지 순회하며 소수가 아닌 수들을 true로 마킹한다.

마킹된 boolean 배열에서 n보다 크고 2n보다 작은 소수를 구해야 하니 n이 소수일 때 n을 소수의 개수로 포함시키면 안된다.
boolean 배열에서 n+1 위치부터 n*2 위치까지 돌며 false의 개수(소수의 개수)를 세면 된다.

작성코드

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        while(true) {
            int n = Integer.parseInt(br.readLine());
            if(n == 0) break;            

            boolean[] prime_arr = new boolean[n*2+1];
            prime_arr[0] = prime_arr[1] = true;

            for(int i=2; i<=Math.sqrt(n*2); i++) {
                for(int j=i+i; j<prime_arr.length; j+=i) {
                    prime_arr[j] = true;
                }
            }

            int cnt = 0;
            for(int i=n+1; i<prime_arr.length; i++) {
                if(prime_arr[i] == false) cnt++;
            }
            bw.write(cnt+"\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• 에라토스테네스의 체를 이용해 소수나 소수의 개수를 구하는 문제를 풀어보며, 소수를 구할 때 가장 효율적인 알고리즘임을 매번 느끼고 있다.