자바) 백준 4948번: 베르트랑 공준

백준 4948번: 베르트랑 공준 (https://www.acmicpc.net/problem/4948)

 

소수 문제이다.

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구한다. 

 

'에라토스테네스의 체 '를 사용 할 수 있다면 복잡하지 않게 풀 수 있다. 

 

순서)

   에라스토테네스 체 작성

-> 체 메서드를 이용하여 2부터 2n 까지의 소수 여부가 기록된 boolean 배열 생성

-> n+1 부터 배열 끝까지 소수를 확인

-> count++조건이 n 보다 커야 하므로 n은 포함시키기 않음.

 

전체코드

package backJoonQ2022year;

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

public class Q4948 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

            boolean[] result = primeArr(caseNum * 2);
            int count = 0;

            // caseNum 보다 크고...
            for (int i = caseNum+1; i < result.length; i++) {

                // result[i]가 false 면 소수
                if (!result[i]) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }
    // 체 메써드, index == 숫자
    private static boolean[] primeArr(int max) {

        // boolean 의 default => false
        boolean[] arr = new boolean[max+1];
        int limit = (int) Math.sqrt(max);

        // 0과 1을 소수가 아님으로 마킹
        arr[0] = true;
        arr[1] = true;

        for (int i = 2; i <= limit; i++) {
            // i가 소수일 경우
            if (!arr[i]) {
                // 소수의 제곱부터 최대범위까지 걸어가며 지운다
                for (int j = i * i; j <= max; j = j + i) {
                    arr[j] = true;
                }
            }
        }
        return arr;
    }
}