#9020 골드바흐의 추측 (c++)

#include <iostream>
#define MAX 10001
using namespace std;

int erastone [MAX];

void check()
{
    for(int i=2; i<MAX; i++)
    {
        if(!erastone[i]) // 0을 의미. 즉, false다.
        {
            for(int j=i*2; j<MAX; j+=i)
            {
                erastone[j]=1; //1은 true다.
            }
        }
    }
    erastone[1] = 1;
}

void Golden(int input)
{
    int a,b=0;
     for(int x=(input>>1); x>1; x--)
     {
         if(!erastone[x])
         {
             for(int y=(input>>1); y<input-1; y++)
             {
                 if(!erastone[y])
                 {
                     if(input==(x+y))
                     {
                         a=x;
                         b=y;
                         cout << a << " " << b << "\n";
                         return;
                     }
                 
                 }
             }
         }
     }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    check();
    int T;
    cin >> T;
    
    for(int i=0; i<T; i++)
    {
        int input;
        cin >> input;
        Golden(input);
    }
    return 0;
}

처음에 모든 테스트 케이스를 통과하고 제출을 해보았으나

시간초과가 나와서 싹 다 갈아엎고 새로 작성해보았다. 

작성하는 과정에서 이것저것 고민해보고, 필요하면 참고도 해보았다. 

결론적으로 수정한 내용은 다음과 같다. 

 

로직 : 입력값의 중간에서부터 하나의 변수는 커지는, 다른 하나의 변수는 작아지는 과정에서 소수를 구한다. 

 

1. 에라스토네스의 체를 void로 작성

2. 입력 값의 중간값을 구하기 위해 비트마스크 연산 적용 (코드가 정말 깔끔해진다) 

3. 상수(const) 사용 

 

이 과정에서 다시 한번 상기 된 기본 개념들을 정리해보자면, 

1. 0은 false를, 1은 true를 의미한다.

2. 비트마스크 연산에서 >>는 해당 값을 오른쪽으로 옮김을 의미 -> 한 번의 이동 당 절반의 값

3. 비스마스크 연산에서 <<는 해당 값을 왼쪽으로 옮김을 의미 -> 한 번의 이동 당 두 배의 값 

4. 객체지향을 기억하자. main하나에 많은 일이 일어나기 보다는 기능들을 큰 단위로 쪼개서 따로 조립하는게 좋다.