[1153] 네 개의 소수

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

다양한 풀이방법이 있겠지만, Goldbach's Conjecture라 불리는 가설?을 이용하여 풀었다.

항상 소수관련문제는 정수론과 뗄레야 뗄 수 없는것 같기도하고..

Goldbach's Conjecture는 아직 증명이 되지않은 정수론 미해결문제중 하나로 "2보다 큰 모든 짝수는 두개의 소수의 합으로 나타낼 수 있다"는 가설이다. 물론 아직 반례를 찾지못해 미해결문제로 남아있다. 즉, 앵간히 큰 짝수(우리가 문제에서 접할 수 있는 수)까지는 다 성립한다는 뜻.

#include <stdio.h>

int num[1000001] = { 0 };

int N;

void prime() {

    for (int i = 2; i*i <= N; i++)

    {

        if (num[i] == 1) continue;

        for (int j = 2; j*i <= N; j++) num[i*j] = 1;

    }

}

void find_prime(int n) {

    int a, b;

    for (int i = 2; i <= N>>1; i++)

    {

        if (num[i] == 0 && num[N - i] == 0) {

            printf("%d %d", i, N - i);

            return;

        }

    }

}

int main() {

    scanf("%d", &N);

    prime();

    if (N < 9) printf("-1");

    else

    {

        if (N & 1) {

            printf("2 3 ");

            N -= 5;

            find_prime(N);

            return 0;

        }

        else

        {

            printf("2 2 ");

            N -= 4;

            find_prime(N);

            return 0;

        }

    }

}