[백준] 4948. 베르트랑 공준

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

구해야하는 소수의 범위는 (주어지는 숫자 + 1, 2 * 주어지는 숫자] 범위.
시간이 1초이기에 브루트포스 방식은 시간 초과 발생

-> 에라토스테네스의 체를 이용해 최대 범위 숫자인 123,456 x 2 만큼의 수가 소수인지를 저장하는 배열 사용
-> 이후 주어지는 수의 x 2 만큼의 배열을 돌면서 소수의 개수가 몇 개 인지 확인.

import java.util.*;
import java.io.*;

public class Main {



    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int[] board = new int[250000];
        board[1] = 1;

        for(int i = 2; i <= 123456; i++) {
            if (board[i] == 0) {
                int mul = 2;
                while (mul * i < 250000) {
                    board[mul * i] = 1;
                    mul++;
                }
            }
        }

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

            int cnt = 0;

            for (int i = num + 1; i <= 2 * num; i++) {
                if (board[i] == 0) {
                    cnt += 1;
                }
            }
            System.out.println(cnt);
        }


    }
}

넉넉하게 250,000의 수를 담을 수 있는 배열 선언하고 에라토스테네스의 체 방법을 이용해 코드 구성 구성