[백준/Java]Q4948

백준 알고리즘 9단계 기본 수학2 4948번 문제입니다.

---

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

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

[조건]
- 각 테스트 케이스에 대해서 n보다 크고 2n보다 작거나 같은 소수의 개수를 출력한다.
- 1 ≤ n ≤ 123456

풀이

이 문제 역시 소수의 연장선에 있어 처음에는 앞서 푼 문제와 같이 접근했다. 하지만 시간 초과에 걸려 다시 생각하게 되었고 에라토스테네스의 체를 이용해 풀어야 한다는 것을 알게 되었다.

먼저 에라토스테네스의 체에 대해 알아봤다.
에라토스테네스의 체 알고리즘은 다음과 같았다.

Ex) 70까지의 소수를 구할 때

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.  (1은 소수가 아니기 때문에 제외)
2. 2는 소수이므로 오른쪽에 2를 쓴다. 자기 자신을 제외한 2의 배수를 모두 지운다. (붉은색)
3. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 자기 자신을 제외한 3의 배수를 모두 지운다. (파란색)
4. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 자기 자신을 제외한 5의 배수를 모두 지운다. (연두색)
   (4는 2의 배수로 이미 지워졌기 때문에 넘어간다)
5. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. 자기 자신을 제외한 7의 배수를 모두 지운다. (노란색)
   (6은 2의 배수로 이미 지워졌기 때문에 넘어간다)
6. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

이 알고리즘을 소스로 구현한다면 아래와 같다.

 

n의 범위가 최대 123456까지이므로 2n까지의 범위로 소수를 담을 배열을 선언했다.
2부터 주어진 수 n까지를 소수로 정의(true)한다. 그리고 반복문을 돌려 2부터 n까지 자신을 제외한 배수를 소수가 아닌 것으로 정의(false)한다.
그렇게 만들어진 배열에서 true의 개수만을 카운트하여 소수의 개수를 구할 수 있다.

 

소스

package com.baek.algo.step09;

import java.util.Scanner;

public class Q4948 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		boolean arr[] = new boolean[246913];

		while(true) {
			int n = sc.nextInt();
			int cnt = 0;

			if(n == 0) {
				break;
			} else {
				int max = n * 2;

				for(int i = 2; i <= max; i++) {
					arr[i] = true;
				}

				for(int i = 2; i <= max; i++) {
					for(int j = i * 2; j <= max; j = j + i) {
						if(arr[j] == true) {
							arr[j] = false;
						}
					}
				}

				for(int k = n + 1; k <= max; k++) {
					if(arr[k] == true) {
						cnt = cnt + 1;
					}
				}

				System.out.println(cnt);
			}
		}

		sc.close();
	}
}