[백준/JAVA] 기본 수학 - 4948번 베르트랑 공준

더 좋은 문제 풀이가 있거나 궁금하신 점이 있다면 편하게 댓글 남겨주세요!

📝 문제

4948번 베르트랑 공준

🤷‍♂️ 접근 방법

지난 시간에 포스팅한 소수 판별법과 같은 문제입니다! [백준/JAVA] 기본 수학2 - 1929번 소수구하기 를 참조하여 볷

✍ 풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        while (true) {
            int n = sc.nextInt();
            int cnt = 0;
            if(n == 0) break;

            boolean check[] = new boolean[2*n +1]; // 0 ~ 2n

            //false 가 소수 true 가 소수가 아닌 수
            check[0] = true;
            check[1] = true;

            //에라토스테네스의 체
            for (int i = 2; i <= Math.sqrt(check.length); i++) {
                //이미 체크한 것이라면
                if(check[i] == true) continue;

                for( int j = i * i; j< check.length; j = j+i){
                    check[j] = true;
                }

            }

            //n보다 크고, 2n보다 작거나 같은 소수
            for(int i = n+1; i< check.length; i++){
                if(check[i] == false) cnt++;
            }
            System.out.println(cnt);

        }

    }
}