BOJ 4948 베르트랑 공준

1 개요

BOJ 4948 베르트랑 공준

• 백준 온라인 저지 4948번 문제
• [[BOJ {{{단계}}}단계]]

[[분류:BOJ {{{단계}}}단계]]

• n이 주어졌을때, n보다 크고 2n보다 작거나 같은 소수를 구하는 문제
• 알고리즘 분류: 에라토스테네스의 체, 구현

2 Java

import java.util.Scanner;
public class Main {
	static boolean is_prime(int n) {
		if( n < 2 ) return false;
		if( n < 4 ) return true;
		if( n%2==0 || n%3==0 ) return false;
		for(int i=5; i*i<=n; i+=6 ) if(n%i==0 || n%(i+2)==0) return false;
		return true;
	}
	static int bertrand_count(int n) {
		int count = 0;
		for(int i=n+1; i<=2*n; i++) {
			if( is_prime(i) ) count++;
		}
		return count;
	}
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n;
		while( true ) {
			n = sc.nextInt();
			if( n == 0 ) return;
			System.out.println( bertrand_count(n) );
		}
	}
}

3 같이 보기

• BOJ 1929 소수 구하기
• BOJ 9020 골드바흐의 추측
• 베르트랑 공준