백준 6588번 C++

백준 6588번 골드바흐의 추측

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

6588번: 골드바흐의 추측

정답 코드

#include <iostream>
#include <math.h>
#define MAX 1000001             

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);     
    cin.tie(nullptr);
    cout.tie(nullptr);

    int prime[MAX] = { 1, };        

    for (int x = 2; x <= sqrt(MAX); x++) {      
        if (prime[x] != 0)
            continue;
        for (int y = x * x; y <= MAX; y += x) {
            prime[y] = 1;
        }
    }

    int n;
    while (1) {
        cin >> n;
        if (n == 0)
            break;
        bool find = false;  
        for (int x = 2; x < n; x++) {
            if (prime[x] == 0 && prime[n - x] == 0) {      
                cout << n << " = " << x << " + " << n - x << '\n';
                find = true;
                break;
            }
        }
        
        }
    }
   

문제 풀이

에라토스테네스의 체를 이용해서 먼저 소수를 판정했습니다. 배열 안의 값이 0이면 소수, 1이면 소수가 아닙니다. 그다음 반복문을 돌리면서 0이 입력되면 종료시키고, 그 안에서 2부터 n까지 반복문을 돌립니다.
n-x+x는 n이기 때문에 arr[n]과 arr[n-x]가 둘 다0일때
골드바흐의 추측이 성립하므로 이 경우마다 출력하였습니다.