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

해결

• 입력값은 최대 123456이지만, 문제내에서 구해야 할 범위는 입력값 두 배이다. 그래서 123456*2 까지의 소수를 구해야 한다.
• 소수 여부 배열을 생성 후, 각 인덱스마다 소수가 몇 개인지 저장하는 배열을 하나 더 생성해서, 해당 배열을 사용하여 소수의 개수를 구한다.

  [참고]
  https://velog.io/@dayoung_sarah/알고리즘-에라토스테네의-체

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 최대 입력값 2배
        boolean[] primeArray = getPrimeArray(123456*2);
        StringBuilder sb = new StringBuilder();
        
        // 누적 소수 갯수
        int cnt=0;
        // 각 숫자마다 누적 소수 갯수 저장할 배열
        int[] cntArray = new int[primeArray.length];
        for(int i=0; i<primeArray.length; i++) {
            if( !primeArray[i] ) {
                cnt++;
            }
            cntArray[i] = cnt;
        }
        
        // 입력값이 0이면 입력 종료
        while(true) {
            int num = Integer.parseInt(br.readLine());
            if( num == 0 ) break;
            
            sb.append(cntArray[num*2] - cntArray[num] + "\n");
        }
        System.out.println(sb);
    }
    
    // 특정 범위 내 소수 여부 배열 구하기
    public static boolean[] getPrimeArray(int max) {
        boolean[] primeArray = new boolean[max + 1];
        primeArray[0] = true;
        primeArray[1] = true;
        
        for(int i=2; i<=Math.sqrt(max); i++) {
            if( primeArray[i] ) continue;
            
            for(int j=i*i; j<primeArray.length; j += i) {
                primeArray[j] = true;
            }
        }
        return primeArray;
    }
}