백준 4948 풀이

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

베르트랑 공준

베르트랑 공준??? 그게 뭔데???

다행히 베르트랑 공준이 무엇인지 몰라도 문제는 풀 수 있었다.

내용은 문제에 있으니 생략하고 대충 범위 내의 소수의 갯수를 구하는 문제이다.

따라서 "에라토스테네스의 체"를 이용하면 쉽게 풀 수 있다.

참고

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

위 링크가 소수 구하기의 기본 문제이니 참고하면 좋을 것 같다.

다시 문제로 돌아가서 반복문을 통해 입력을 받는데 마지막줄에 0을 입력받으면 종료되도록 하면 된다.
이 때 매 반복문마다 필요한 배열을 만들고 소수의 개수를 구하자니 너무 번거롭고 메모리 낭비가 심한것 같아 입력받기 전에 최대 크기의 배열을 만들고 미리 소수인 수와 소수가 아닌 수를 구분했다.

끝.

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

public class Main {
    static int count = 0;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        final int LEN = 246913;

        boolean prime[] = new boolean[LEN];
        for (int i = 0; i < LEN; i++) {
            prime[i] = true;
        }

        prime[0] = false;
        prime[1] = false;

        for (int i = 2; i < LEN; i++) {
            for (int j = 2; i * j < LEN; j++) {
                prime[i * j] = false;
            }
        }

        ArrayList<Integer> list = new ArrayList<>();

        while (true) {
            String num = br.readLine();
            int n = Integer.parseInt(num);
            if (n == 0)
                break;
            int count = 0;
            for (int i = n+1; i <= 2 * n; i++) {
                if (prime[i])
                    count++;
            }
            list.add(count);
        }

        for (Integer tmp : list) {
            bw.write(Integer.toString(tmp) + "\n");
        }

        br.close();
        bw.close();
    }

}