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

문제 링크: 9020번 골드바흐의 추측

https://www.acmicpc.net/problem/9020

 

먼저 아리스토텔레스의 체를 통해 소수인지의 여부를 담고있는 배열을 만들어준다. 투 포인터를 사용하여, left와 right가 모두 처음에는 n/2를 가리키도록 한다. left를 1씩 감소시키며 그 때마다 right를 갱신하면서, 두 포인터가 가리키는 숫자가 모두 소수가 맞는가를 확인한다. 즉 합(n)이 정해져 있는 경우는 한 쪽(left)만 생각한다.

 

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
    	/* 아리스토텔레스의 체 만들기 */
        boolean[] pr = new boolean[10001]; // true: 합성수
        pr[1] = true;
        for (int i = 2; i <= 10000; i++) {
            int j = i * 2;
            while (j <= 10000) {
                pr[j] = true;
                j += i;
            }
        }

		/* 골드바흐 파티션 찾기 */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());
        StringBuilder answer = new StringBuilder();
        for (int t = 0; t < test; t++) {
            int n = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());
            int left = n / 2;
            int right = n - left;
            while (left >= 2) {
                if (!pr[left] && !pr[right]) // left, right가 모두 소수인지를 확인
                    break;
                right = n - --left; // left를 감소시키면 right는 자동으로 갱신
            }
            answer.append(left).append(' ').append(right).append('\n');
        }
        System.out.print(answer);
    }
}

 

Python

arr_size = 10001
arr = [True] * arr_size # true: 소수, false: 합성수
for i in range(2, arr_size):
    # i가 합성수라면 고려할 필요가 없다.
    if not arr[i]:
        continue

    # i가 소수라면, i*k(k>=2인 자연수)는 모두 합성수이다.
    for j in range(i*2, arr_size, i):
        arr[j] = False

cases = int(input())

for i in range(cases):
    n = int(input())

    # left를 n//2부터 1씩 줄여나가면서, n - left가 소수인지 체크
    left = n//2
    while (not arr[left]): left -= 1 # left가 소수가 아니면 소수로 할당
    right = 0

    while True:
        right = n - left # n - left 체크
        if arr[right]: break

        left -= 1
        while (not arr[left]): left -= 1 # left가 소수가 아니면 소수로 할당

    print(left, right)