[백준] 6588. 골드바흐의 추측 <C++>

 

1. 우선 입력받을 때마다 소수를 찾으면 200%의 확률로 시간 초과가 납니다.

   에라토스를 써줍시다.

//에라토스 코드
  for(int i=2; i*i<1000000; i++)
  {
    if(arr[i]==0)
    for(int j=i*i; j<1000000; j+=i)
    {
      arr[j]=1;
    }
  }

 

 

 

 

2. C++언어를 쓰는 분들은 보통 cin을 이용하여 입력을 받습니다. cin은 시간이 오래 걸리죠.  

   입력 시간을 줄여줍시다.

  cin.tie(NULL);
  ios_base::sync_with_stdio(0);

 

 

 

 

3. 입력을 받아 소수인 두 수를 찾아주어야 하는데 모든 소수를 볼 필요는 없습니다. 

   저는 인덱스를 지정해줄 변수 두 개를 써서 시간을 줄였습니다.

    left=3;
    right=n-3;

    while(left <= right)
    {
      if(!arr[left] && !arr[right])
        if((left+right) == n)
          break;
      left+=2;
      right-=2;
    }

 

 

 

 

 

전체 코드

#include <iostream>
using namespace  std;

int arr[1000001]={1,1,1,0,};

int main() {
  int n, left, right;

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

  cin.tie(NULL);
  ios_base::sync_with_stdio(0);

  while(1)
  {
    cin>>n;
    if(!n) break;

    left=3;
    right=n-3;

    while(left <= right)
    {
      if(!arr[left] && !arr[right])
        if((left+right) == n)
          break;
      left+=2;
      right-=2;
    }

    if(left>right)  cout<<"Goldbach's conjecture is wrong.";
    else cout<<n<<" = "<<left<<" + "<<right<<'\n';
  }
}