[백준 9020]-[수학] - 골드바흐의 추측

문제링크 : https://www.acmicpc.net/problem/9020

---

이 문제는 에라토스테네스의 체의 확장 문제이다. 

에라토스테네스의 체 문제는 이전글에서 확인하면 된다.

2018/11/27 - [알고리즘/수학] - [백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java)

이 문제를 접근하는 방법은 입력받은 수 N을 구성하는 두 소수의 합을 구하면 된다.

두 소수의 합이 여러가지가 있다면 두 수의 차가 제일 적을 수를 구하면 된다. 

그럼 N 보다 작은 모든 소수들을 찾아서 합해야하나 하지만 그렇지 않아도 된다. 

N 의 절반인 수를 기준으로 하나의 수는 1씩 감소하고 다른 하나는 1씩 증가하면서 두 수가 실수 인경우를 찾으면 위의 조건을 모두 만족한다. 

입력받은 수가 16인 경우를 테이블로 보자.

16
a	b
8	8
7	9
6	10
5	11
4	12
3	13
2	14
1	15

두 소수의 합이 16인 경우는 {5, 11}, {3, 13} 두 경우가 있다. 그리고 두 수의 차가 제일 작은것 {5, 11} 이다.

처음 a 와 b를 N의 절반인 8로 초기화하고 a는 1씩 차감 b는 1씩 증가 시키면서 두 수가 소수인경우 를 보면 두 수의 차가 제일 작은{5, 11} 에 먼저 도달한다.

그럼 바로 반복문을 종료시키고 출력시키면 된다.

int N = Integer.parseInt(br.readLine());
            
for(int i = N/2; i > 0; i--) {
    int idx1 = i;
    int idx2 = N - i;
    if(!isnt_prime_num[idx1] && !isnt_prime_num[idx2]) {
        sb.append(idx1 + " " + idx2 + "\n");
        break;
    }
}

전체소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static int MAX = 10000;
    public static boolean[] isnt_prime_num;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        isnt_prime_num = new boolean[MAX+1];
        getPrimeNum();
        int size = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        for(int t=0; t < size; t++) {
            int N = Integer.parseInt(br.readLine());
            
            for(int i = N/2; i > 0; i--) {
                int idx1 = i;
                int idx2 = N - i;
                if(!isnt_prime_num[idx1] && !isnt_prime_num[idx2]) {
                    sb.append(idx1 + " " + idx2 + "\n");
                    break;
                }
            }
        }
        System.out.println(sb.toString());
    }
 
    public static void getPrimeNum() {
        isnt_prime_num[1] = true;
        
        for(int i=2; i <= MAX; i++) {
            for(int j=2; i*j <= MAX; j++) {
                isnt_prime_num[i*j] = true;
            }
        }
    }
}