[백준 4948]-[수학] - 베르트랑 공준

문제링크 : https://www.acmicpc.net/problem/4948

---

이 문제는 에라토스테네스의 체를 이용해서 푸는 좀 심화 문제라고 생각하면 된다. 

2018/11/27 - [알고리즘/수학] - [백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java)

먼저 이문제를 풀기전에 입력수의 크기는 12345 라고 하고 베르트랑의 공준이 어떤 내용인지 설명해주고 있다.

n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

배열의 범위를 123456 로만 하면 인덱스가 초과되서 런타임에러가 발생한다.

최소 범위 123456 * 2 값인 246912 + 1 을 해야한다. 

문제를 푸는 순서는 다음 순서를 따른다.

1) 에라토스테네스의 체로 2부터 246912 까지의 소수를 구한다.

2) 위의 구한 소수의 배열로 새로운 배열에 2 ~ 246912까지의 존재하는 소수의 수를 저장한다.

3) 입력받은 값의 2N 까지의 소수의 수와 N까지의 소수의 수를 뺀 값을 출력한다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static int MAX = 246912; // 입력되는 수의 최대값이 123456 이니깐 2N 까지는 구해야 한다.
    
    public static boolean[] isNot_pNum;
    public static int[] pNumCntArr;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        isNot_pNum = new boolean[MAX+1];
        pNumCntArr = new int[MAX+1];
        
        getPrimeNum();
        
        StringBuilder sb = new StringBuilder();
        
        while(true) {
            int num = Integer.parseInt(br.readLine());
            if(num == 0) break;
            
            sb.append((pNumCntArr[num*2] - pNumCntArr[num]) + "\n");
        }
        
        System.out.println(sb.toString());
        
        br.close();
    }
 
    public static void getPrimeNum() {
        // 소수 구하기
        isNot_pNum[1] = true;
        
        for(int i=2; i <= MAX; i++) {
            for(int j=2; i*j <= MAX; j++) {
                isNot_pNum[i*j] = true;
            }
        }
        // 0 ~ i 까지(최대:MAX) 까지의 수까지 존재하는 실수의 수를 구한다. 
        for(int i=2; i <= MAX; i++) {
            pNumCntArr[i] = pNumCntArr[i-1];
            if(!isNot_pNum[i]) pNumCntArr[i]++;
        }
    }
}