9020)골드바흐의 추측

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

골드바흐의 추측은 어떤 짝수가 두 개의 소수 합으로 나타낼 수 있다는 주장이다.

예를들어 4는 2와2의 합으로 표현될 수 있다.

16은 5와 11의 합으로 표현될 수 있다.

일단 짝수 n이 주어지면 2로 나누고 몫이 소수인지 확인한다.

몫이 소수가 아니면 n을 다른 소수합으로 표현하되 그 소수의 차이가 최소가 되게 해야한다.

간단한 아이디어로 해결할 수 있다.

위 그림처럼 16은 2로 나눈 몫은 소수가 아니지만 두 수의 합은 16을 만든다.

왼쪽 수를 i라하고 오른 쪽 수를 j라할 때 i,j가 소수이면서 j-i가 0에 가깝게 만들면 된다.

i를 1씩 감소시키면 합은 일정하게 유지되야하기 때문에 j는 1씩 커져야 한다.

i가 감소하고 j가 증가할 때 두 수가 소수인지를 체크하기만 하면 된다.

굳이 차이가 최소인지를 확인할 필요는 없는데 두 소수의 차이가 0부터 차례로 증가시켰기 때문이다.

#include<stdio.h>
#define TRUE 1
#define FALSE 0
 
int isPrime(int num) {
    int isPrime = TRUE;
    if (num == 1) return FALSE;
    for (int i = 2; i < num; i++) {
        if (num%i == 0) {
            isPrime = FALSE;
            break;
        }
    }
    return isPrime;
}
 
int main() {
    int T, n;
    int i, j;
    
    scanf("%d",&T);
    for (int k = 0; k < T;k++) {
        scanf("%d",&n);
        i = j = n/2;
 
        if (!isPrime(i)) {
            do {
                i--; j++;
            } while (!(isPrime(i) && isPrime(j)));
        }
 
        printf("%d %d\n", i, j);
    }

    return 0;
}