백준 4948 : 베르트랑 공준 _자바 Java

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

4948번: 베르트랑 공준

---

*에라토스테네스의 체 : https://apple-concrete-344.notion.site/8a3a0d31c84e4f6b8f0f6c17621490b1

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

public class Main {

	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true) {
			int N=Integer.parseInt(br.readLine());
						
			if(N==0)
				break;
			
			boolean[] prime = new boolean[N*2+1];
			Arrays.fill(prime, true);
			prime[0]=false;
			prime[1]=false;
			
			int cnt=0;
			
            //에라토스테네스의 체
			for(int i=2;(i*i)<=2*N;i++) {
				if(prime[i]) {
					for(int j=i*i;j<2*N+1;j+=i) {
						prime[j]=false;					
					}
				}
				
			}
			
			
			for(int i=N+1; i<(2*N+1); i++) {
				if(prime[i] == true) {
					cnt++;
				}
			}
			System.out.println(cnt);
		}
		
	}// main()
	
	
}// class Main