6588번

6588번 - 골드바흐의 추측

에라토스테네스의 체를 응용한 문제라고 볼 수 있다.

이 문제를 풀면서 문제점

1. 에라토스테네스의 체를 한번만 써도 되는데 while 문 안에 넣어서, 반복적으로 계산하게 함 -> 시간 초과를 야기함.

2. while 문 안에 반복적으로 에라토스테네스 체를 쓰면서 vector 및 변수를 초기화 안함 -> 메모리 초과를 야기함.

3. 차이를 최대로 하는 두 소수를 구하는 방법

=> 이미 N이 주어져 있기 때문에 v[i] 의 최소값만 구하고, N-v[i] 의 값이 소수인지만 확인이 된다면 

문제에서 요구하는 b-a 가 최대이고 , 둘다 홀수 소수인 값이 결정이 되는데, 

무식하게 이중 for문을 통해서 모든 b-a를 구해서 최대값일 때마다 변경하는 수고를 하다보니, 엄청난 시간 초과를 야기했다.

이중 for문을 하나의 for문으로 바꾸는 이번 스킬은 몸에 잘 습득해야겠다.

< 정답 코드 >

#include<iostream>
#include<vector>

 
using namespace std;
 
bool check[1000001];
bool isPrimeNum[1000001];
 
int main()
{
    int N;
    vector<int> v;
 
    for (int i = 2; i <= 1000000; i++)
    {
        if (!check[i])
        {
            isPrimeNum[i] = true;
 
            if (i % 2 == 1)
            {
                v.push_back(i);
            }
 
            for (int j = i * 2; j <= 1000000; j += i)
            {
                check[j] = true;
            }
        }
    }
    
    while (scanf("%d",&N) && N != 0)
    {
 
        int diff = -987654321;
        int x, y;
        for (int i = 0; i < v.size()-1; i++)
        {
            if (isPrimeNum[N - v[i]])
            {
                y = v[i];
                x = N - v[i];
                diff = x - y;
                break;
            }
        }
 
        if (diff != -987564321)
        {
            printf("%d = %d + %d\n", N, y, x);
        }
        else
        {
            printf("Goldbach's conjecture is wrong.\n");
        }
 
    
    }
 
    return 0;
}