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

문제

 

 

에라스토테네스의 체

https://skylarcoding.tistory.com/361

 

문제 반례 찾는 법

아래 링크에서 확인할 수 있다.

https://skylarcoding.tistory.com/303

 

 

코드

package AlgorithmStudy.src.silver;

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

public class S4948 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = 1;
        while (n != 0) {
            n = Integer.parseInt(br.readLine());
            if (n != 0) {
                isPrime(n);
            }
        }
    }

    public static void isPrime(int n) {
        boolean[] list = new boolean[2 * n + 1];
        int cnt = 0;

        list[0] = true;     // 소수 아님
        list[1] = true;

        for (int i = 2; i * i<= 2 * n; i++) {
            if (!list[i]) {
                for (int j = i * i; j <= 2 * n; j += i) {
                    list[j] = true;
                }
            }
        }

        for (int i = n + 1; i <= 2 * n; i++) {
            if (!list[i]) {
                cnt ++;
            }
        }
        System.out.println(cnt);
    }
}

 

 

해설

기본적인 에라스토테네스의 체 코드에 대한 설명은 아래 포스팅을 보면 된다.

https://skylarcoding.tistory.com/361

 

베르트랑 공준에서 좀 더 심화 설명으로 나아가자면, 입력받은 n 과 2n 사이의 소수를 구해야 하는게 추가적인 내용이다. for 문에서 마지막 숫자가 2 * n 값임을 변경해주면 된다.

 

기존에 소수일 경우 출력하던 값은 cnt 를 추가하여 소수일 경우 cnt 를 증가하여, 마지막에 cnt 값만 나오면 된다.

 

소수 구하기와 매우 유사한 문제이다.