[BOJ][실1][9020] 골드바흐의 추측

문제 링크

소수 구하기/실2

첫 번째 풀이 : 소수

알고리즘

Info Notice: 소수를 판별하는 방법1은 소수가 아닙니다. 25를 생각했을 때 2~5(제곱급)까지의 수 중에서 25를 나누어 떨어지게 하는 수가 있으면 안됩니다. 1과 자기 자신만 약수일 수 있기 때문입니다. 또는 에라토스테네스의 체를 사용합니다.

이미 소수인지 판별해두었기 때문에 O(N)으로 진행할 수 있습니다.

정답 코드

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int n = 0;
const int MAX = 10010;
bool isPrime[MAX+1];

int main(void) {
    //freopen("input.txt", "r", stdin);
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = false;
    // MAX까지 소수인지 아닌지 판단
    for (int curr = 2; curr <= MAX; curr++) { // curr : MAX의 약수 후보
        if (isPrime[curr]) {
            for (int next = curr * curr; next <= MAX; next += curr) {
                isPrime[next] = false;
            }
        }
    }
    int tc = 0;
    cin >> tc;
    while (tc--) {
        int n = 0; cin >> n;
        int a = 0, b = 0, diff = 987654321;
        for (int i = 2; i <= n / 2; i++) {
            if (!isPrime[i]) continue;
            if (isPrime[n - i]) {
                if (diff > (n - i) - i) {
                    a = i;
                    b = n - i;
                }
            }
        }
        cout << a << " " << b << "\n";
    }
    return 0;
}

Success Notice: 소수 개념을 사용한 문제를 풀어봤습니다. 수고하셨습니다.