4948_베르트랑 공준 (JAVA)

4948번: 베르트랑 공준

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int num = sc.nextInt();
			if(num == 0)
				break;

			System.out.println(ans(num));
		}
	}
	public static int ans(int num){
		int cnt=0;
        
		boolean[] check = new boolean[num*2+1];
		for(int i=2; i<=num*2; i++){
			check[i] = true;
		}

		for(int i=2; i<=num*2; i++){
			if(!check[i])
				continue;
			for(int j=i+i; j<=num*2; j+=i){
				check[j] = false;
			}
		}

		for(int i=num+1; i<=num*2; i++){
			if(check[i])
				cnt++;
		}
		return cnt;
	}
}

 

[문제 풀이 생각 과정] - 에라토스테네스의 체 이용

 

 

 

• 유사 문제

[백준] 1929_소수 구하기 (Silver2) (JAVA)