[Baekjoon] 6588_골드바흐의 추측

Silver I

문제(출처: https://www.acmicpc.net/problem/6588)

---

< 골드바흐의 추측 >

 

문제 풀이 

 

에라토스테네스의 체를 활용하여 미리 소수를 판별해 둔다. 수를 입력받아 2부터 (입력받은 수/2)까지 탐색하여 소수의 합으로 나타낼 수 있는지 확인한다.

 

 my solution (Java)

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

public class _6588_ { // 골드바흐의 추측

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		boolean arr[] = new boolean[1000001];
		for (int i = 2; i <= 500001; i++) {
			if (!arr[i]) {
				for (int j = i + i; j < 1000001; j += i) {
					arr[j] = true;
				}
			}
		}

		int num = 0;
		while ((num = (Integer.parseInt(bf.readLine()))) != 0) {
			int x = 0, y = 0;
			for (int i = 2; i <= num / 2; i++) {
				if (!arr[i] && !arr[num - i]) {
					x = i;
					y = num - i;
					break;
				}
			}
			if (x != 0 && y != 0) {
				bw.write(num + " = " + x + " + " + y + "\n");
			} else {
				bw.write("Goldbach's conjecture is wrong.\n");
			}
		}
		bw.flush();
	}
}

변수)
arr : 소수 판별
num : 입력받은 값
x, y : num을 이루는 값

 

에라토스테네스의 체를 사용하여 1000000까지 소수를 판별한다. 0이 아닐 때까지 값을 입력받는다. 2부터 (정수/2)까지 탐색하면서 소수의 합으로 나타낼 수 있는지 판별한다. b-a가 가장 큰 것을 출력하라고 했으므로 2부터 탐색하면서 값을 찾으면 바로 종료하면 된다. 만약 10을 찾는데 3+7, 5+5 두 가지 경우가 있다면 3+7이 b-a가 큰 값이다. b-a값이 크려면 작은 값부터 판별하면 된다. 두 홀수 소수의 합으로 값을 나타낼 수 있다면 값을 출력하고, 나타낼 수 없다면 "Goldbach's conjecture is wrong."을 출력한다.

---

---