[백준 6588] 골드바흐의 추측

www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

에라토스테네스의 체를 사용하여 1000000까지 소수를 체크하고

주어진 입력 t의 양끝점을 확인하여 start + end == t 가 되는 지점을 확인한다.

#include <stdio.h>

using namespace std;
int t;

int arr[10000001];
int main(void)
{

  for (int i = 2; i * i <= 1000000; i++)
  {
    if (arr[i])
      continue;
    for (int j = i << 1; j <= 1000000; j += i)
    {
      arr[j] = 1;
    }
  }

  while (1)
  {
    scanf("%d", &t);
    if (t == 0)
    {
      break;
    }
    int start = 3, end = t;
    bool flag = false;
    while (start <= end)
    {
      while (arr[end])
      {
        end--;
      }

      while (arr[start])
      {
        start++;
      }

      if (end + start == t)
      {
        flag = true;
        printf("%d = %d + %d\n", t, start, end);
        break;
      }
      else if (end + start > t)
      {
        end--;
      }
      else
      {
        start++;
      }
    }

    if (!flag)
    {
      printf("Goldbach's conjecture is wrong.\n");
    }
  }
  return 0;
}