[백준][Java] 4948번 베르트랑 공준

방금 전에 익힌 에라토스테네스의 체를 이용하여 문제를

해결합니다.

주의해야할 점은 boolean배열을 하나만 이용하여

문제를 해결해야한다는 점입니다.

저 같은 경우는 getprime메소드 안에

boolean 배열을 넣어 소수를 구할 때마다

배열을 선언해야 하는 바람에 한번 틀렸습니다.

크기 또한 문제에서 요구하는 n<=123456인 점을 감안하여

2*n+1 크기의 배열을 만들어주시면 됩니다. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

import java.util.*; public class Main { static boolean[] res = new boolean[246913]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); res[0]=res[1]=true; while(true) { int n=sc.nextInt(); if(n==0) break; System.out.println(getPrime(n)); } } private static int getPrime(int n) { int res_num=0; for(int i=2; i<Math.sqrt(2*n); i++) { if(!res[i]) { for(int j=2 ; i*j<=2*n ;j++ ) { res[i*j]=true; } } } for(int i=n+1;i<=2*n;i++) { if(!res[i]) res_num++; } return res_num; } }