위의 문제를 요약하면, 베르트랑 공준은 임의의 자연수 n에 대해
n과 2n 사이에는 무조건 소수가 존재하는 것을 뜻한다.
풀이는 아래와 같다.
이전에 풀었던 BackJoon 1929 소수구하기 문제에서
범위만 변경 됬을뿐이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//베르트랑 공준
//n 과 2n 사이의 소수 갯수 구하기
public class BJ_4948 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
int count = 0;
int n = Integer.parseInt(br.readLine());
if (n < 1 || n > 123456) return;
if (n == 0) break;
outer:
for (int i = n + 1; i <= 2 * n; i++) {
int dividend = (int) Math.sqrt(i); // 특정 수가 2개의 수의 곱이라 했을때 둘중하나는 무조건 제곱근보다 작거나 같다.
while (dividend > 1) { // 그리고 특정 수의 소수인 약수들의 배수가 특정 수의 약수라면 그 특정수는 소수가 아니다.
if (i % dividend-- == 0) continue outer;
}
if (dividend == 1 && i != 1) ++count; // 나누기가 마무리 됬을때, 피제수가 1이라면 도중에 나눠떨어지는수가 없었다는걸 의미한다.
}
if(count == 0) return;
System.out.println(count);
}
}
}