[백준(Baekjoon)][자바(java)] (4948) 베르트랑 공준 / 수학 2

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
        
		int i, j, n, cnt;
		boolean a[];
        
		while( true ) {
        
			cnt = 0;
			n = sc.nextInt();
			if( n == 0 )	break;
			a = new boolean[2*n+1];
            
			for( i = 2; i <= 2*n; i++ ) 
				a[i] = true;
                
			for( i = 2; (i*i) <= 2*n; i++ ) 
				if( a[i] ) 
					for( j = (i*2); j <= 2*n; j+=i )	
						a[j] = false;
                        
			for( i = n+1; i <= 2*n; i++ ) 
				if( a[i] )
					cnt++;
                    
			System.out.println( cnt );
		}	
	}
}