[BOJ/6588/C++] 골드바흐의 추측

👀 문제

 

[문제 요약]

n = a + b (a, b -> 홀수 소수)
- 경우의 수가 여러가지: b - a 가 가장 큰 것
- 없으면 : "Goldbach's conjecture is wrong." 출력

---

📝 접근 방법

1. 소수를 에라토스테네스의 체를 이용해서 미리 배열에 구해놓는다.
2. b - a가 가장 큰 것 (= a가 작은 것)
   이므로 a를 3 에서부터 n / 2까지 올라가면서 구한다.
   (2도 소수이지만 문제에서 홀수 소수라고 했으므로..., 같은 의미로 a는 홀수만 검사한다.)
3. a, b가 둘 다 소수일 경우에 n = a + b를 출력하고, found 플래그를 참으로 한 후 해당 반복문에서 빠져나온다.
4. 반복문을 다 돈 이후에 found 플래그가 false 일 경우 "Goldbach's conjecture is wrong." 를 출력한다. 

 

---

😎 해결 코드

#include <iostream>
#include <vector>
#define MAX 1000000
using namespace std;

vector<bool> isPrime(MAX + 1, true); 

void sieve() {
    isPrime[0] = isPrime[1] = false;

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

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

    sieve();

    while (true) {
        int n; cin >> n;
        if (n == 0) break;

        bool found = false;

        for (int a = 3; a <= n / 2; a += 2) {
            int b = n - a;
            if (isPrime[a] && isPrime[b]) {
                cout << n << " = " << a << " + " << b << '\n';
                found = true;
                break;
            }
        }

        if (!found) {
            cout << "Goldbach's conjecture is wrong." << '\n';
        }
    }
}

 

---

⚠️ 틀리거나 시간이 오래 걸린 이유

좀 많이 틀렸는데..

그냥 습관적으로 에라토스테네스의 체가 아니라 isPrime 함수로 매번 소수가 맞는지 확인하는 방식으로 짜서 시간 초과가 났다

 

소수인지 판별해야 하는 대상이 많을 때에는 에라토스테네스의 체 사용하기...~

---

📚 배운 점

- 에라토스테네스의 체