[백준 JAVA] 4948번 풀이 - 베르트랑 공준
by mini_minpackage quiz;
import java.io.BufferedReader;
import java.io.InputStreamReader;
/**
* 4948번 풀이 - 베르트랑 공준
* 베르트랑 공준은 임의의 자연수 n에 대하여,
* n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
* 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
* 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19)
*
* 자연수 n이 주어졌을 때, n보다 크고 2n보다 작거나 같은 소수의 개수를 구하여라.
*
**/
public class _4948 {
public static void main(String[] args) throws Exception {
//입력은 여러 개의 테스트 케이스로 이루어져 있다.
//입력의 마지막은 0이다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true){
int n = Integer.parseInt(br.readLine());
if (n == 0) break;
//n < target <= 2n
int[] arr = new int[(2*n) + 1];
int count = 0;
for ( int i = 2; i <= 2*n; i++ ) {
arr[i] = i;
}
for ( int i = 2; i <= Math.sqrt(2*n); i++ ){
if (arr[i] == 0) {continue;}
//특정 수 배수 지우기.
for ( int j = i + i; j <= 2*n; j+= i ){
arr[j] = 0;
}
}
for (int i = n+1; i <= 2*n; i++) {
if (arr[i] != 0) {
//System.out.println(arr[i]);
count++;
}
}
System.out.println(count);
}
}
}
풀이
"에라토스테네스의 체" 를 이용해서 풀었다.
배열은 2부터 2n까지.
2n의 제곱근까지 수의 배수를 지워버리고, 출력만 n < target <= 2n 을 조회해서 뽑았다.
'매일매일 알고리즘 공부' 카테고리의 다른 글
[백준 JAVA] 9012번 풀이 - 괄호 (✨✨✨) (0) | 2023.10.05 |
---|---|
[백준 JAVA] 17103번 풀이 - 골드바흐 파티션 (골드바흐의 추측) (1) | 2023.09.25 |
[백준 JAVA] 1929번 풀이 - 소수 구하기 (에라토스테네스의 체) (0) | 2023.09.13 |
[백준 JAVA] 4134번 풀이 - 다음 소수 (0) | 2023.09.06 |
[백준 JAVA] 2485번 풀이 - 가로수 🌟 (0) | 2023.09.03 |
블로그의 정보
개발자 미니민의 개발로그
mini_min