[JAVA] 백준 6588번

6588번 - 골드바흐의 추측

 

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

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));

		boolean[] check = new boolean[1000001];
		check[0] = check[1] = true;

		for (int i = 2; i < check.length; i++) {
			if (!check[i]) {
				for (int j = 2; i * j < check.length; j++) {
					check[i * j] = true;
				}
			}
		}

		int n = Integer.parseInt(br.readLine());

		while (n != 0) {

			boolean mProve = false; // 골드바흐 증명이 가능한경우 true, 불가능한경우 false

			for (int k = 2; k <= n / 2; k++) {
				if (!check[k]) { // 소수인 경우
					if (!check[n - k]) {
						bw.write(n + " = " + k + " + " + (n - k));
						bw.newLine();
						mProve = true;
						break;
					}
				}

			}

			if (!mProve) {
				bw.write("Goldbach's conjecture is wrong.");
				bw.newLine();
			}

			n = Integer.parseInt(br.readLine());
		}

		bw.flush();
		bw.close();
	}

}

 

처음 문제에 접근한 방식

1. 입력된 n의 값만큼 소수값을 판별할 배열을 생성

2. 에라토스테네스의 체를 통해 소수를 구하여 저장

3. 입력된 n의 절반의 값까지 오름차순으로 소수를 구하고 구한 소수를 n에서 뺀값이 n이라면 출력

 

정답을 맞춘 풀이방법

1 . 매번 n의 값만큼 배열을 입력하니 시간초과 발생 미리 100만까지의 배열을 선언한 이후 재사용 하면서 판별함

2. 에라토스테네스의 체를 통해 소수를 구하여 저장

3. 입력된 n의 절반의 값까지 오름차순으로 소수를 구하고 구한 소수를 n에서 뺀값이 n이라면 출력