[백준 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)