백준 4948번 자바 문제 답/해설(베르트랑 공준 문제)

[1] 백준 카테고리

단계별로 풀어보기

기본 수학 2
5단계 4948번 문제
베르트랑 공준

[2] 문제

베르트랑 공준은 임의의 자연수 n에 대해서, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

임명제는 조졔프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10 보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17, 19 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

1. 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

2. 출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

 

3. 제한

1 ≤ n ≤ 123,456

4. 예제 입력 1
1
10
13
100
1000
10000
100000
0

5. 예제 출력 1

1
4
3
21
135
1033
8392

 

[3] 정답
1. 정답 해설 미포함

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true) {
			int n = Integer.parseInt(br.readLine());			
			if(n==0) {
				break;
			}

			boolean[] prime = new boolean[2*n+1];
			prime[0] = true;
			prime[1] = true;
			int count = 0;

			for(int i=2; i<=(2*n+1); i++) {
				for(int j=i*i; j<2*n+1; j+=i) {
					prime[j] = true;
				}
			}
			for(int i=n+1; i<(2*n+1); i++) {
				if(prime[i] == false) {
					count++;
				}
			}
			System.out.println(count);
			}
	}
}

2. 정답 해설 포함

import java.io.BufferedReader;
/* BufferedReader 사용을 위해서 java.io.BufferedReader 클래스를 import 한다
Enter를 경계로 인식하고 받은 데이터는 String으로 고정된다.*/
import java.io.InputStreamReader;
/* byte 단위 데이터를 문자 단위 데이터로 처리할 수 있도록 변환해주기 위해서
InputStreamReader를 사용한다.
InputStreamReader 사용을 위해서 java.io.InputStreamReader 클래스를 import 한다.*/
import java.io.IOException;
/* 예외 처리를 위해서 IOException를 사용한다.
IOException 사용을 위해서 java.io.IOException 클래스를 import 한다.*/

public class Main {
// 접근제어자 public으로 Main 클래스를 선언한다.
	public static void main(String[] args) throws NumberFormatException, IOException {
	// 접근제어자 public으로 메모리에 상주하게 int형 변수 N 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader 객체 br를 선언
		while(true) {
		// 괄호안의 코드를 무한 반복한다.
			int n = Integer.parseInt(br.readLine());
			// int 형 변수 n를 선언하고 Enter를 기준으로 값을 입력받아 저장한다.
			if(n==0) {
			// n==0일때 괄호안의 코드를 실행
				break;
				// while문을 탈출한다.
			}

			boolean[] prime = new boolean[2*n+1];
			// boolean형 배열 prime을 선언하고 길이를 2*n+1으로 한다.
			prime[0] = true;
			// boolean 형 변수 prime[0]에 값 true 저장
			prime[1] = true;
			// boolean 형 변수 prime[1]에 값 true 저장
			int count = 0;
			// int형 변수 count에 값 0 저장

			for(int i=2; i<=(2*n+1); i++) {
			// i가 2~2*n+1일때 괄호 안에 코드를 반복
				for(int j=i*i; j<2*n+1; j+=i) {
				// j가 i*i~<2*n+1 일때 괄호 안의 코드를 반복
					prime[j] = true;
					// 변수 prime[j]에 값 true 저장
				}
			}
			//에라스토텔레스의 채 부분 n의 배수를 걸려낸다.
			
			for(int i=n+1; i<(2*n+1); i++) {
			// i가 n+1~<2*n+1일때 괄호 안의 코드를 반복
				if(prime[i] == false) {
				// prime[i] == false일때 괄호 안의 코드를 실행
					count++;
					// count+1한 값을 변수 count에 저장
				}
			}
			System.out.println(count);
			// 변수 count에 저장된 값을 출력
			}
	}
}