[수학] BOJ 6588번 골드바흐의 추측

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

- 문제 풀이

에라토스테네스의 체로 미리 홀수 소수를 구하고 입력이 들어올 때 마다 n - (홀수 소수) 를 계산하여 결과가 홀수 소수인 값을 출력한다.

 

 

- 문제 풀이시 중요한 것

문제 풀이는 맞았으나 cin 함수의 사용때문에 코드 자체가 느려서 시간초과가 발생했다.

cin.tie(NULL);
ios::sync_with_stdio(false);

 

위 두 코드는 cin 의 시간을 상당히 줄여준다.

 

이전까지 채점이 버벅이는 부분이 있었는데 이것 때문이였다..

 

- 정답

#include "bits/stdc++.h"

using namespace std;

int n;
int arr[1000005];

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    for (int i = 3; i < 1000000; i++)
    {
        if (i % 2 != 1) continue;
        if (arr[i] > 0) continue;

        arr[i] = 2; // 모든 홀수 소수는 2
        for (int j = 2; i * j < 1000000; j++)
        {
            arr[i * j] = 1;
        }

    }

    while (1)
    {
        cin >> n;

        if (n == 0) break;

        int tmp = -1;

        for (int i = 3; i < 1000000; i++)
        {
            if (arr[i] == 2)
            {
                tmp = n - i;

                if (arr[tmp] == 2)
                {
                    //8 = 3 + 5
                    cout << n << " = " << i << " + " << tmp << "\n";
                    break;
                }
            }
        }

        if(tmp == -1)
            cout << "Goldbach's conjecture is wrong.";


    }
}