Problem Solving/Java
백준 6588번 골드바흐의 추측 에라토스 테네스의 체 활용 문제풀이 ( Java )
TakeKnowledge
2019. 10. 22. 16:20
반응형
6588번: 골드바흐의 추측
문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모
www.acmicpc.net
|
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
|
public class Main {
public static final int MAX = 1000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// reader writer 생성
int n;
int a;
int b;
boolean[] isNotPrime = new boolean[MAX + 1];
// 소수 판별 배열 선언
isNotPrime[0] = true;
isNotPrime[1] = true;
// 0과 1 제외
for (int i = 2; i < MAX; i++) {
if (isNotPrime[i] == false) {
// 소수 찾으면
for (int j = i + i; j <= MAX; j += i) {
isNotPrime[j] = true;
// 그 배수들 소수가 아니라 표시
}
}
}
// MAX까지 소수 판별하고
while ((n = Integer.parseInt(br.readLine())) != 0) {
for (int i = 3; i < n; i++) {
// 표시된 소수 배열 3부터 돌면서
if (isNotPrime[i] == false) {
// 소수 찾으면
a = i;
// a를 소수에 넣고
if (isNotPrime[n - a] == false) {
// n-a가 aㄱ n-a번째 배열도 소수면
b = n - a;
// b도 찾았으니
bw.write('\n');
// 출력하고
break;
// 반복문 탈출
}
}
}
}
}
}
|
처음엔 n을 받을 때마다 소수 판별을 했더니 시간 초과가 나왔다
그래서 아예 MAX까지 소수를 구해놓고 입력 받을 때 마다 골드바흐의 추측만 증명했더니 클리어
반응형