[백준] 4948번. 베르트랑 공준(JAVA)

문제

https://www.acmicpc.net/problem/4948

---

풀이(17분)

import java.io.*;
import java.util.*;
public class Main {

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

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

            System.out.println(eratosthenesCount(2*testCase));
        }
    }

    public static int eratosthenesCount(int x){
        boolean[] isPrime = new boolean[x + 1];
        for(int i = 0; i < isPrime.length; i++){
            isPrime[i] = true; // boolean배열의 default값은 false이므로 true로 바꿔주기
        }
        isPrime[0] = isPrime[1] = false;
        for(int i = 2; i <= Math.sqrt(x); i++){ // 2부터 n의 제곱근까지의 모든 수를 확인
            if(isPrime[i]){ // 해당수가 소수라면, 해당수를 제외한 배수들을 모두 false 처리하기
                for(int j = i*i; j<= x; j += i){//그 이하의 수는 모두 검사했으므로 i*i부터 시작
                    isPrime[j] = false;
                }
            }
        }

        int count = 0;
        for(int i = 2; i < x + 1; i++){
            if(isPrime[i]){
                count++;
            }
        }
        int answer = count;

        count = 0;
        for(int i = 2; i < x/2 + 1; i++){
            if(isPrime[i]){
                count++;
            }
        }
        answer -= count;
        return answer;
    }
}

 

기존 에라토스테네스의 체를 알고 있다면 문제 해결 자체에 어려움이 있을 거라고는 생각하지 않는다.

먼저 2배의 숫자에 대해 소수 체크를 전부 진행한 후 이에 대해 반복문을 통해 개수를 세서 빼주면 된다.

에라토스테네스의 체를 잘 모른다면 이 글을 참고하자. https://to-travel-coding.tistory.com/83

[도구정리] 에라토스테네스의 체