백준 9020번 문제(골드바흐의 추측) C++로 풀기

9020번 골드바흐의 추측 링크

---

문제 요약

주어진 n의 골드바흐 파티션을 출력한다.

---

코드

#include <iostream>

using namespace std;

const int range=10001;

int main()
{
  int nums[range]={0,};
  for(int j=2;j<range;j++)
  {
    nums[j]=j;
  }
  for(int k=2;k<range;k++)  // 에라토스테네스의 체
  {
    if(nums[k]==0) continue;
    for(int l=2*k;l<range;l+=k)
    {
      nums[l]=0;
    }
  }
  int t;
  scanf("%d",&t);
  while(t!=0)
  {
    int n;
    scanf("%d",&n);
    int g1,g2;  //  골드바흐 파티션
    for(int h=n/2;h<n;h++)
    {
      if(nums[h]!=0 && nums[n-h]!=0)  // 파티션끼리 차이가 적게 하기 위함
      {
        g2=nums[h];
        g1=n-g2;
        break;
      }
    }
    printf("%d %d\n",g1,g2);
    t--;
  }
}

---

풀이

소수를 문제 범위까지 만들고, 최소 차이가 나는 골드바흐 파티션을 출력한다.
파티션끼리 차이가 최소로 나기 위해, 입력받은 수 n을 절반으로 나눠 n/2부터 n까지에서 n/2와 가장 가까운 소수를 찾았다.

---

주의점

파티션끼리 차이가 최대한 적게 나야한다.