[백준 6588번] 골드바흐의 추측

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

6588번: 골드바흐의 추측

풀이) 

1929(소수 구하기)와 같은 방법으로, 소수 구하는 알고리즘을 다시 사용했다. 미리 입력값 범위에 해당하는 소수를 다 구해놓고 i와 n - i가 소수인지 확인한 후 출력해주었다. 차이가 가장 커야하므로 결과가 나오면 바로 탈출시켜주었다.

#include <iostream>
using namespace std;

int prime[1000001];
int is_prime(int n)
{
    int i;

    if (n < 2)
        return (0);
    i = 2;
    while (i <= n / 2 && i <= 1000)
        if (n % i++ == 0)
            return (0);
    return (1);
}

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

    int n;
    for (int i = 2; i <= 1000000; i++)
        prime[i] = is_prime(i);
    while (1)
    {
        cin >> n;
        if (!n) break;
        for (int i = 2; i < n; i++)
        {
            if (prime[i] && prime[n - i])
            {
                cout << n << " = " << i << " + " << n - i << "\n";
                break ;
            }
        }
    }
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!