[문제]백준 9020번 골드바흐의 추측

* 출처: 백준 단계별로 풀어보기 기본 수학2

www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

소수 문제! 

우선 에레토스테네스의 체를 이용해 prime 배열을 초기화 시켜준다.

이후, 두 소수의 합이 n이 되는 쌍을 찾으면 되는 것이다. n = first + second라고 할 때,

여기서 n을 절반으로 나눈 다음, first는 n/2에서 하나씩 줄여가고, second는 n/2에서 하나씩 증가시키면서 찾아가면 된다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	public static boolean[] prime;
	public static int MAX_NUM = 10000;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(in.readLine());
		int N = 0;
		prime = new boolean[MAX_NUM + 1];
		initPrime();

		for (int i = 0; i < T; i++) {
			N = Integer.parseInt(in.readLine());
			int ans[] = new int[2];
			getGold(N, ans);
			sb.append(ans[0]).append(' ').append(ans[1]).append('\n');
		}

		System.out.println(sb);
	}

	static void initPrime() {
		prime[0] = prime[1] = true;

		for (int i = 2; i <= Math.sqrt(MAX_NUM); i++) {
			if (prime[i])
				continue;
			for (int j = i * i; j <= MAX_NUM; j += i) {
				prime[j] = true;
			}
		}
	}

	static void getGold(int n, int[] ans) {
		int first = n/2;
		int second = n/2;
		while(true) {
			if(!prime[first] && !prime[second]) {
				ans[0] = first;
				ans[1] = second;
				return;
			}
			first --;
			second++;
		}
	}
}

 

아래는 내가 푼 코드인데, 위의 코드의 시간보다 약 두 배가 더 걸린다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	public static boolean[] prime;
	public static int MAX_NUM = 10000;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(in.readLine());
		int N = 0;
		prime = new boolean[MAX_NUM + 1];
		initPrime();

		for (int i = 0; i < T; i++) {
			N = Integer.parseInt(in.readLine());
			int ans[] = new int[2];
			getGold(N, ans);
			sb.append(ans[0]).append(' ').append(ans[1]).append('\n');
		}

		System.out.println(sb);
	}

	static void initPrime() {
		prime[0] = prime[1] = true;

		for (int i = 2; i <= MAX_NUM; i++) {
			if (prime[i])
				continue;
			if (i * i > MAX_NUM)
				break;
			for (int j = i * i; j <= MAX_NUM; j += i) {
				prime[j] = true;
			}
		}
	}

	static void getGold(int n, int[] ans) {
		boolean isCheck[] = new boolean[n];

		for (int i = 2; i <n; i++) {
			if (isCheck[i])
				break;
			if (!prime[i]) {
				int x = i;
				int y = n - i;
				if (!prime[y]) {
					ans[0] = x;
					ans[1] = y;
					isCheck[x] = true;
					isCheck[y] = true;
				}
			}
		}
	}

}