문제
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하며, 한 줄로 이루어져 있다. (n ≤ 123456)
입력의 마지막에는 0이 주어진다.
출력
각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
| 예제 입력 1 1 10 13 100 1000 10000 100000 0 |
예제 출력 1 1 4 3 21 135 1033 8392 |
문제풀이
전체적인 소스코드는 이전 포스트와 동일하다
그래서 달라진 부분만 설명하도록 하겠다.
먼저 입력을 받는 방식이 달라졌다. 0을 입력받을 때까지만 입력받아야 하므로 arraylist를 써서 0을 입력받을 때까지만 리스트에 추가해준다.
그 후 iterator 컬렉션을 arr리스트의 iterator를 사용하기 위해 선언해준다.
그리고 while문을 이용해서 iterator의 다음 요소가 있을 때까지만 동작한다. 그리고 start에는 들어온 숫자를 넣어주고
end에는 start*2를 해서 2n을 만들어준다.
그리고 베르트랑 공준에는 한가지 특이한 점이 있는데 start는 포함되지 말아야 한다는 점이다. 따라서 start가 아닌 start+1부터 반복문을 돌리면서 소수를 카운팅해줘야 한다.
이하 소수를 구하는 부분은 에라토스테네스의 체를 이용하여 진행하였다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
import java.io.*;
import java.util.ArrayList;
import java.util.Iterator;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n;
ArrayList<Integer> arr = new ArrayList<>();
while ((n = Integer.parseInt(br.readLine())) != 0) arr.add(n);
Iterator<Integer> iterator = arr.iterator();
while (iterator.hasNext()) {
int start = iterator.next();
int end = start * 2;
boolean[] sieve = new boolean[end + 1];
boolean isContainTrue;
int cnt = 0;
// sieve를 true로 초기화
for (int i = 0; i < sieve.length; i++) sieve[i] = true;
// 에라토스테네스의 체
// i는 배수의 시작 수
for (int i = 2; i < sieve.length; i++) {
isContainTrue = false;
// 주어진 범위내의 숫자들 중 소수로 판별한다.
for (int j = start + 1; j <= end; j++) {
if (sieve[j - 1] == true) {
isContainTrue = true;
break;
} }
// 주어진 범위내의 소수가 존재한다면 다시 체로 거른다.
if (isContainTrue) {
// j는 i의 곱셈 수(first부터 시작할 수 있도록 한다.)
for (int j = 2; i * j < sieve.length; j++) {
sieve[i * j - 1] = false;
}
// 주어진 범위내의 소수가 존재하지 않는다면 탈출한다.
} else {
break;
}
}
// 체로 걸러진 숫자들을 출력한다.(단, 1은 소수가 아니므로 제외한다.)
for (int i = start + 1; i < sieve.length; i++) {
if (sieve[i - 1] == true && i != 1) {
cnt++;
// bw.write(i + "\n");
// bw.flush();
}
}
bw.write(cnt+"\n");
bw.flush();
}
bw.close();
}
}
|
cs |
|
|
|
느낀점
에라토스테네스의 체를 이용한다면 굉장히 쉬운문제
'백준 온라인 저지 문제풀이 > JAVA' 카테고리의 다른 글
| [baekjoon 1085번] 수학 2 - 직사각형에서 탈출 (0) | 2020.12.17 |
|---|---|
| [baekjoon 9020번] 수학2 - 골드바흐의 추측 (0) | 2020.12.17 |
| [baekjoon 1929번] 수학 2 - 소수 구하기 (0) | 2020.12.15 |
| [baekjoon 1978번] 수학 2 - 소수 찾기 (0) | 2020.12.14 |
| [baekjoon 1011번] 수학 1 - Fly me to the Alpha Centauri(2) (0) | 2020.12.12 |