알고리즘
[백준 알고리즘] 4948 - 베르트랑 공준
DevBee
2021. 6. 24. 06:04
https://www.acmicpc.net/problem/4948
4948번: 베르트랑 공준
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼
www.acmicpc.net
문제는 위와 같으면 이 문제는 다른 소수 문제들과 마찬가지로 먼저 에라토스테네스의 체를 통해 123456 * 2 수까지의 소수를 구한 다음, 0이 입력될 때까지 반복문을 돌면서 (주어진 숫자 + 1)부터 (주어진 숫자 * 2)까지 수 중 소수가 있는지 확인하여 소수인 경우 개수를 증가시키고 이 개수를 나중에 출력하는 방식으로 해결할 수 있습니다.
자바 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
// 소수인 경우 true, 아닌 경우 false
boolean[] primeNum = new boolean[(123456 * 2) + 1];
Arrays.fill(primeNum, true);
primeNum[0] = primeNum[1] = false;
for (int i = 2; i * i < primeNum.length; i++) {
for (int j = i * i; j < primeNum.length; j += i) { // i를 제외한 i의 배수를 찾아 false로 변경
primeNum[j] = false;
}
}
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
int n = Integer.parseInt(br.readLine());
// 0인 경우 입력 종료
if (n == 0) {
break;
}
int count = 0;
// n 보다 크고 2n 보다 작거나 같은 소수 찾아서 수 세기
for (int i = n + 1; i < (n * 2) + 1; i++) {
if (primeNum[i]) {
count++;
}
}
sb.append(count).append("\n");
}
// 출력
System.out.print(sb);
}
}