백준 #1153 네 개의 소수

골드바흐의 추측과 관련해서는 한두번 이상은 들어보았을겁니다.  유명한 문제이긴 하지만 아직 증명이 안 되었죠.  사실 수학적 가치가 크다고 볼 수는 없는 문제입니다.  쉽게 증명될 것이라는 예상과는 달리 아직까지 미해결 문제입니다.

 

Goldbach's Number(from Wikipedia)

 

골드바흐의 추측은 2보다 큰 수는 세개의 소수의 합으로 만들 수 있다였습니다.  사실 당시에는 1이 소수로 취급되었을 때였기 때문에, 3=1+1+1, 4=2+1+1, 5=2+2+1 로 표현이 가능했습니다.  현대 소수 개념으로는 6이상의 수는 세개의 소수의 합으로 표현할 수 있다입니다.

 

이번 문제는 Gold IV 난이도입니다.

 

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

1153번: 네 개의 소수

전 이 문제를 풀기 위해서 트릭을 사용했습니다.  뭐, 어차피 골드바흐는 반례를 찾지 못한 이상, 우리가 컴퓨터로 일반적으로 표현할 수 있는 범위내에서는 골드바흐 추측은 참입니다.  그래서 늘 골드바흐 추측은 성립한다는 가정을 하면 됩니다.  100미만의 숫자들에 대한 골드바흐 추측을 미리 계산해서 기록한 후에, 숫자 범위에 따라서 소수는 하나만 찾고, 나머지는 미리 계산된 숫자들을 이용했습니다.

 

그렇게 해서 나온 소스는 이렇습니다.  참고용으로 봐주세요.

//------------------------------------------------------------------------------
//  baekjoon #1153 - Four primes
//    - by Aubrey Choi
//    - created at 2019-12-26
//------------------------------------------------------------------------------
#include <stdio.h>

//  (6,99) Goldbach's primes.
const int gb[][3]={2,2,2, 2,2,3, 2,3,3, 2,2,5, 2,3,5, 2,2,7, 2,3,7, 3,3,7, 2,5,7, 
  2,2,11, 2,3,11, 2,2,13, 2,3,13, 3,3,13, 2,5,13, 2,2,17, 2,3,17, 2,2,19, 2,3,19, 
  3,3,19, 2,5,19, 2,2,23, 2,3,23, 3,3,23, 2,5,23, 3,5,23, 2,7,23, 2,2,29, 2,3,29, 
  2,2,31, 2,3,31, 3,3,31, 2,5,31, 3,5,31, 2,7,31, 2,2,37, 2,3,37, 3,3,37, 2,5,37, 
  2,2,41, 2,3,41, 2,2,43, 2,3,43, 3,3,43, 2,5,43, 2,2,47, 2,3,47, 3,3,47, 2,5,47, 
  3,5,47, 2,7,47, 2,2,53, 2,3,53, 3,3,53, 2,5,53, 3,5,53, 2,7,53, 2,2,59, 2,3,59, 
  2,2,61, 2,3,61, 3,3,61, 2,5,61, 3,5,61, 2,7,61, 2,2,67, 2,3,67, 3,3,67, 2,5,67, 
  2,2,71, 2,3,71, 2,2,73, 2,3,73, 3,3,73, 2,5,73, 3,5,73, 2,7,73, 2,2,79, 2,3,79, 
  3,3,79, 2,5,79, 2,2,83, 2,3,83, 3,3,83, 2,5,83, 3,5,83, 2,7,83, 2,2,89, 2,3,89, 
  3,3,89, 2,5,89, 3,5,89, 2,7,89, 3,7,89 };
int main()
{
  int n, i, p;
  scanf("%d",&n);
  if(n<8) { puts("-1"); return 0; }
  if(n<102) {n-=8; printf("2 %d %d %d\n",gb[n][0],gb[n][1],gb[n][2]);return 0;}
  if(n<188) {n-=95; printf("%d %d %d 89\n",gb[n][0],gb[n][1],gb[n][2]);return 0;}
  for(p=n-99+(n&1);;p+=2)
  {
    for(i=3;i*i<=p;i+=2) if(p%i==0) break;
    if(i*i>p) break;
  }
  n-=p+6; printf("%d %d %d %d\n",gb[n][0],gb[n][1],gb[n][2],p);
}