백준 4948번 : 베르트랑 공준 [Java]

문제 링크 : https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

문제 |

 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17, 19, 23)
 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

 

입력 |

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

 

출력 |

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

 

제한 |

• 1 ≤ n ≤ 123,456

import java.io.*;

public class Main {
	public static boolean[] checkbox = new boolean[246913];
	
	public static void prime_made() {
		for(int i = 2; i <= Math.sqrt(checkbox.length); i++) {
			if(checkbox[i]) continue;
			for(int j = i * i; j < checkbox.length; j = j + i) {
				checkbox[j] = true;
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int input = Integer.parseInt(br.readLine());
		
		prime_made();
		
		int count;
		
		while(input != 0) {
			count = 0;
			for(int i = input + 1; i <= input * 2; i++) {
				if(checkbox[i] == false)
					count++;
			}
			System.out.println(count);
			input = Integer.parseInt(br.readLine());
		}
	}
}

 주력 언어가 이번 문제부터는 Java로 바뀌게 되었다. 최근에 Spring 공부를 하고 있어서 Java를 자주 사용할 것 같아 주력 언어를 바꾸게 되었다.

 베르트랑 공준 문제는 단계별로 풀기의 기본 수학에 포함되어 있는 문제인데 소수를 구하는 문제의 연장선이다. 입력한 값으로부터 2배만큼 되는 값 사이에 있는 숫자들 중 소수의 숫자를 세어 출력하는 문제로 요약할 수 있다. 나는 앞선 소수 구하기 문제에서 공부한 에라토스테네스의 체를 사용하여 소수를 구하는 메소드를 이용해 문제를 풀어보도록 하겠다.

 

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int input = Integer.parseInt(br.readLine());
		
		prime_made();

 먼저 입력을 받는 부분이다. 원래는 Scanner를 처음에 사용했는데 BufferedReader를 사용하니까 입출력으로 인한 시간 초과 판정을 받을 일이 많이 줄어들었다. 그 이후부터는 BufferedReader를 입력문으로 많이 애용한다. input이라는 int형 변수에 입력 값을 정수형으로 받아 넣고 prime_made()라는 메소드를 실행시킨다. prime_made() 메소드는 에라토스테네스의 체를 구현한 메소드이다.

 

	public static boolean[] checkbox = new boolean[246913];
	
	public static void prime_made() {
		for(int i = 2; i <= Math.sqrt(checkbox.length); i++) {
			if(checkbox[i]) continue;
			for(int j = i * i; j < checkbox.length; j = j + i) {
				checkbox[j] = true;
			}
		}
	}

 문제에서 주어진 예제를 보면 처음에 입력을 한 번 받고 끝나는 것이 아닌, 여러 개의 입력을 받기 때문에 처음에 에라토스테네스의 체를 이용해 모든 범위의 소수 여부를 구해놓고 그 뒤에 소수로 판정난 것만 세는 것이 효율적이라고 판단했다.

 Main 클래스 내 전역 변수로 선언한 checkbox는 참, 거짓을 구별할 수 있는 boolean 자료형의 배열인데 소수 판별 범위가 입력받은 값의 2배까지기에 최대로 받을 수 있는 123,456의 2배인 246912에다 마지막 null 값이 들어가는 것을 방지하기 위해 1을 더한 246913의 크기로 설정하였다.

 prime_made() 메소드에서는 본격적으로 소수 판별을 시작하는데 true면 소수가 아니고, false면 소수이다. 기본적으로 boolean형 배열에는 false값이 들어가 있다. 

 외부 for문에서는 2부터 배열 최대 크기의 제곱근까지(에라토스테네스의 체)의 소수들을 찾아낸다. 그리고 안의 if문에서는 검사하는 배열의 값이 true일 경우, 그러니까 소수가 아닐 경우에는 따로 내부 for문을 작동시키지 않고 다음 값으로 넘어가게끔 continue를 넣었다.

 내부 for문이 작동되는 경우는 외부 for문에서의 i값이 소수이기 때문에 작동되는 것이다. 그러므로 i값을 제곱한 j값(j = i * i)부터 i값만큼 늘어나는 곳(j = j + i)에다가 true값을 넣어 이것들은 소수가 아님을 표시해준다. 그래서 i값은 소수로 남고 i의 제곱값부터 i값만큼 늘어나는 수들은 전부 소수가 아닌 수가 된다.

 

		int count;
		
		while(input != 0) {
			count = 0;
			for(int i = input + 1; i <= input * 2; i++) {
				if(checkbox[i] == false)
					count++;
			}
			System.out.println(count);
			input = Integer.parseInt(br.readLine());
		}

 다시 메인 메소드로 돌아와서 이제 입력값에 따른 소수의 개수를 알아내도록 하자.

 문제에서 0이 주어지면 프로그램의 동작이 멈추어야하므로 while문 조건에 0이 입력되면 반복문을 빠져나가도록 하였다. 그리고 다음 입력값의 소수 개수를 새로 계산하게끔 매번 count 변수를 0으로 초기화하도록 하였다.

 for문에서는 문제에서 입력값'보다 큰'이라고 했으므로 입력값은 범위에 들어가지 않는다. 따라서 for문에서 입력값에 1을 더한 값부터 입력값의 2배 이하까지 검사하도록 하였다. 여기서 false로 표기된 소수만 걸러내어 count 값을 증가시켰다.

 for문의 동작이 멈추면 count에 저장된 소수의 개수를 출력하고 다음 입력값을 받도록 하였다.