[백준] 6588번 : 골드바흐의 추측

문제

 

---

풀이

 

홀수인 두 소수의 합으로 짝수를 나타내는 문제이다.

 

홀수인 두 소수이므로 3부터 시작하면 될 것이고 입력값의 절반까지만 탐색하면 된다.

만약 입력이 8이라면 3+5와 5+3은 같은 말이기 때문이다.

 

그리고 두 소수의 차가 가장 큰 것을 출력하라고 했는데 그럼 뭐 3부터 탐색하다가 두 소수를 찾으면 바로 출력하면된다.

20은 3+17로도 나타낼 수 있고 7+13으로도 나타낼 수 있지만 두 수의 차가 가장 큰 것은 먼저 발견된 3+17이다.

 

이 소수를 찾는 과정에서 시간초과가 나지 않도록 빠르게 구하는 것이 중요하다.

나는 에라토스테네스의 체를 사용했다.

 

myunji.tistory.com/61

[백준] 1929번 : 소수 구하기

여기에서 구현했었다.

 

처음엔 input이 들어올 때마다 에라토스테네스의 체를 실행했는데 시간초과가 발생했다.

생각해보니 max input이 1000000이므로 처음에 그냥 그 범위의 수에 대한 에라토스테네스의 체를 실행하면 되는 일이었다.

---

소스코드

 

#include <iostream>
#include <cmath>

using namespace std;
const int MAX = 1000000;

bool isPrime[MAX];

void eratos() { //에라토스테네스의 체
    fill(isPrime+2, isPrime+MAX, 1); //0과 1은 소수가 아님

    int line = sqrt(MAX) + 1; //제곱근까지만 계산
    for (int i = 2; i <= line; i++) {
        if (isPrime[i]) { //소수의 배수들을 모두 false 처리
            for (int j = i * 2; j < MAX; j += i)
                isPrime[j] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int input;

    eratos(); //미리 소수 전부 찾아 놓음
    while (true) {
        bool isGoldbach = false;

        cin >> input;
        if (input == 0) //종료조건
            break;
        for (int i = 3; i <= (input / 2); i++) { //3부터 input의 절반까지 소수 탐색
            if (isPrime[i] && isPrime[input - i]) {
                isGoldbach = true;
                cout << input << " = " << i << " + " << input - i << '\n';
                break;
            }
        }
        if (!isGoldbach) //소수의 합으로 나타낼 수 없음
            cout << "Goldbach's conjecture is wrong.\n";
    }
}

전체 소스코드다.

 

const int MAX = 1000000;

bool isPrime[MAX];

void eratos() { //에라토스테네스의 체
    fill(isPrime+2, isPrime+MAX, 1); //0과 1은 소수가 아님

    int line = sqrt(MAX) + 1; //제곱근까지만 계산
    for (int i = 2; i <= line; i++) {
        if (isPrime[i]) { //소수의 배수들을 모두 false 처리
            for (int j = i * 2; j < MAX; j += i)
                isPrime[j] = false;
        }
    }
}

input을 받기 전 1000000보다 작은 모든 소수를 찾아낸다.

 

    eratos(); //미리 소수 전부 찾아 놓음
    while (true) {
        bool isGoldbach = false;

        cin >> input;
        if (input == 0) //종료조건
            break;
        for (int i = 3; i <= (input / 2); i++) { //3부터 input의 절반까지 소수 탐색
            if (isPrime[i] && isPrime[input - i]) {
                isGoldbach = true;
                cout << input << " = " << i << " + " << input - i << '\n';
                break;
            }
        }
        if (!isGoldbach) //소수의 합으로 나타낼 수 없음
            cout << "Goldbach's conjecture is wrong.\n";
    }

3부터 시작해서 a, b 둘 다 소수인 경우를 찾으면 바로 출력하고 break 한다.