[JAVA/백준/4948] 베르트랑 공준 / 에라토스테네스의 체

4948번: 베르트랑 공준

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼

www.acmicpc.net

이전에 풀었던 1978 문제와 풀이는 거의 똑같았다.

에라토스테네스의 체를 이용하여 소수를 찾고 입력값의 두 배만큼만 탐색하면 된다.

에라토스테네스의 체는 아래의 글을 참고한다.

[JAVA/백준/1978] 소수 찾기 - 에라토스테네스의 체

풀이 방법 소수를 빠르게 찾는 방법은 에라토스테네스의 체라는 유명한 방법이 있다. 1. 1은 소수가 아니므로 제외한다. 2. 2는 소수이므로 소수 목록에 추가한다. 2의 배수는 소수가 아니므로

comibird.tistory.com

결과

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


public 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));
    Boolean[] num = new Boolean[123456 * 2 + 1];
    Arrays.fill(num, true);
    num[1] = false;
    
    
    // 123456의 두 배 크기의 배열 생성
    // 소수의 배수는 false 처리
    for (int i = 2; i < 123456 * 2 + 1; i++) {
      if (num[i] == true) {
        for (int j = i * 2; j < 123456 * 2 + 1; j += i) {
          num[j] = false;
        }
      }
    }
    
    // 입력이 0이 될 때까지 무한 반복
    // 입력값 초과, 입력값 * 2 이하의 수 중 소수의 개수를 출력
    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 (num[i] == true) {
          count++;
        }
      }
      bw.write(count + "\n");
    }
    bw.flush();
    br.close();
  }
}