[백준 / BOJ] - 9020번 골드바흐의 추측 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [9020] 

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

문제

 

 

2보다 큰 짝수 n이 주어졌을 때, 가장 작은 차이가 나는 두 소수의 합으로 표현을 하려고 한다. 이 때 두 소수를 구하고 출력하는 프로그램을 작성하는 문제이다.

 

풀이

 

에라토스테네스의 체를 이용하여 소수 판별 배열을 만들고, N/2를 중심으로, N/2 - i과 N/2 + i 모두가 소수가 되도록 하는 i의 값을 찾고, N/2 - i 와 N/2 + i의 값을 출력하면 쉽게 해결할 수 있다.

 

 

 

코드

 

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int num, max = 0;
    cin >> num;
    int* even = new int[num];
    for(int i = 0; i < num; i++) {
        cin >> even[i];
        if(even[i] > max)
            max = even[i];
    }
    bool *prime = new bool[max+1];
    fill_n(prime, max + 1, 1);
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i <= sqrt(max); i++)
        if(prime[i] == true)
            for(int j = i*2; j <= (max); j += i)
                prime[j] = false;

    for(int t = 0; t < num; t++)
    {
        for(int j = even[t]/2; j > 0; j--)
        {
            if(prime[j] && prime[even[t]-j])
            {
                cout << j << ' ' << even[t]-j << '\n';
                break;
            }
        }
    }
}

 

평가

 

에라토스테네스의 체를 활용한 문제이다. N/2 - i 와 N/2 + i의 합은 언제나 N이 된다는것을 활용하여 풀이가 가능하다.