[C++/백준] 6588번: 골드바흐의 추측

문제 링크

6588번: 골드바흐의 추측

 

풀이

소수 문제인데 시간 초과로 꽤나 머리 아팠던 문제

1. 먼저 최대 숫자인 1000000까지 소수를 체크하기 위한 배열을 정의한다. 소수가 아닐 경우 true이다.
2. 에라토스테네스의 체를 통해 소수인지 체크한다.
   1. 첫번째 반목문에서 1000000의 제곱근까지만 구해도 내부 반목문에서 해당 숫자의 제곱부터 배수를 체크할 것이다.
   2. sosu[i]가 true라면 소수가 아닌 것으로 이미 체크가 된 것이므로 continue
   3. 2번이 해당되지 않으면 해당 숫자는 소수이고, 그 소수의 제곱부터 배수들을 소수가 아닌 것으로 체크한다.
   4. 왜 배수를 체크하는데 제곱부터 구하냐면, 해당 수보다 작은 숫자의 배수는 그 전 숫자들에서 구했을 것이므로 중복된다. 예를 들어 j가 5라면 배수인 2부터 진행되어야 할텐데, j가 2일 때 5배수를 체크했을 것이므로 해당 숫자보다 같거나 큰 배수만 체크해줌
3. 그렇게 소수를 다 체크하면 n이 0이 될 때까지 입력을 받는다.
4. i는 3부터 n이 될 때 까지 홀수만 구한다. i는 a가 될 것이다. 이렇게 하는 이유는 짝수는 구할 필요 없으니 3부터 2씩 더해 홀수만 구한다.
5. 그렇게 sosu[i]와 sosu[n-i]가 소수라면 출력한다.
6. 모든 검색이 끝나도 flag가 false라면 문자열을 출력한다.

 

코드

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    bool sosu[1000001] = { false, };
    sosu[0] = true;
    sosu[1] = true;

    // 에라토스테네스의 체
    for (int i = 2; i * i < 1000001; i++)
    {
        if (sosu[i]) continue;
        for (int j = i * i; j < 1000001; j += i)
        {
            sosu[j] = true;
        }
    }

    while (true)
    {
        int n;
        cin >> n;
        if (n == 0) break;

        bool flag = false;
        for (int i = 3; i < n; i+=2)
        {
            if (!sosu[i] && !sosu[n - i])
            {
                flag = true;
                cout << n << " = " << i << " + " << n-i << '\n';
                break;
            }
        }
        if (!flag)
        {
            cout << "Goldbach's conjecture is wrong.\n";
        }
    }
}