알고리즘 풀이/백준

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

배게 2018. 4. 30. 02:05
728x90

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

해결합니다.


주의해야할 점은 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;
	}
}