[백준, 자바, 4948번] 베르트랑 공준

풀이

• 해당 문제는 특정 정수보다 크면서 2배한 것 보다 작거나 같은
• 모든 소수를 구하는 문제로서
• 입력값은 0이 나올 때까지 받기에
• 우선은 모든 입력 값을 배열에 담아두면서
• 가장 큰 값을 찾고, 이후에 큰 값의 2배에 해당 하는 배열을 만들어서
• 모든 소수를 에라토스테네스의 체를 활용하여 판별한 뒤
• 이후 배열을 돌려가며 범위에 해당하는 소수를 카운팅하여 해결.

 

import java.io.*;
import java.util.*;
public class _4948 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        List<Integer> li = new ArrayList<>();
        int mx = 0;
        while (true) {
            int N = sc.nextInt();
            if (N==0) break;
            li.add(N);
            if (N>mx) mx = N;
        }
        boolean[] prime = new boolean[2*mx+1];
        prime[1]=true;
        for (int i=2; i<2*mx; i++) {
            for (int j=i*2; j<=2*mx; j+=i) {
                if (!prime[j]) prime[j]=true;
            }
        }

        for (int num: li) {
            int cnt = 0;
            for (int i=num+1; i<=2*num; i++) {
                if (!prime[i]) cnt++;
            }
            bw.write(cnt+"\n");
        }
        bw.flush();
    }
}