[백준][C++] 9020: 골드바흐의 추측

문제

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

풀이

수학, 에라토스테네스의 채, 소수 판정

 

• 소수 판정에는 에라토스테네스의 채를 사용하여, 알고리즘 시작 전에 10000까지 소수를 판정해 둔다. 
• 두 소수의 차이가 가장 적은 것을 출력해야 하므로, 시작 값(start)을 n / 2로 설정하여, 중앙에 가장 가깝도록 한다. 
• start를 1씩 감소 시키면서, n - start가 소수라면 해당 값이 차이가 가장 적은 소수이므로 이를 출력하고 알고리즘을 중지한다. 

처음에는 두 포인터로 문제를 해결하였지만, 위의 방법이 더 효율적이였다. 

코드

방법 1

#include <iostream>
#include <memory.h>

using namespace std;

const int MAX = 4'000'001;

bool prime[MAX];

// 에라토스테네스의 체
// N까지의 수 중 소수는 true로 표시
void eratosthenes(int N)
{
    memset(prime, false, sizeof(prime));

    for (int i = 2; i <= N; ++i)
    {
        prime[i] = true;
    }

    for (int i = 2; i * i <= N; ++i)
    {
        if (prime[i])
        {
            for (int j = i * i; j <= N; j += i)
            {
                prime[j] = false;
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    eratosthenes(10000);

    int T;
    cin >> T;

    while (T--)
    {
        int n;
        cin >> n;

        // n / 2 부터 탐색 시작
        int start = n / 2;

        for (int i = start; start >= 2; --start)
        {
            // start와 n - start가 소수라면 정답이므로 바로 break
            if (prime[start] == true && prime[n - start] == true)
            {
                cout << start << " " << n - start << '\n';
                break;
            }
        }
    }

    return 0;
}

 

방법 2

#include <iostream>
#include <memory.h>

using namespace std;

const int MAX = 4'000'001;

bool prime[MAX];

// 에라토스테네스의 체
// N까지의 수 중 소수는 true로 표시
void eratosthenes(int N)
{
    memset(prime, false, sizeof(prime));

    for (int i = 2; i <= N; ++i)
    {
        prime[i] = true;
    }

    for (int i = 2; i * i <= N; ++i)
    {
        if (prime[i])
        {
            for (int j = i * i; j <= N; j += i)
            {
                prime[j] = false;
            }
        }
    }
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    eratosthenes(10000);

    int T;
    cin >> T;

    while (T--)
    {
        int n;
        cin >> n;

        int start = 2;
        int end = n;
        int answer_start = 2;
        int answer_end = n;
        int diff = n - 2;

        while (start <= end)
        {
            if (prime[start] == false)
            {
                start++;
                continue;
            }
            if (prime[end] == false)
            {
                end--;
                continue;
            }

            if (start + end == n)
            {
                if (end - start < diff)
                {
                    answer_start = start;
                    answer_end = end;
                    diff = end - start;
                }
                start++;
                end--;
            }
            else if (start + end > n)
            {
                end--;
            }
            else
            {
                start++;
            }
        }

        cout << answer_start << " " << answer_end << '\n';
    }

	return 0;
}