(C++) - 백준(BOJ) 6588번 : 골드바흐의 추측

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

6588번: 골드바흐의 추측

수학문제였습니다.

 

풀이방법

 1. 에라토스테네스의 체를 이용해 i번째 수가 소수인 부분은 0 아닌 부분은 1로 ck배열에 저장합니다.

 2. 답 출력 : i와 n-i가 모두 소수라면(ck배열에 해당 값이 0이라면) 정답을 출력합니다.

 

* 수학적으로 100만 이하의 소수 두 개의 합으로 모든 짝수를 표현할 수 있습니다. 따라서 안되는 경우는 없습니다. 낚시입니다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n;
int ck[1000001];

void makePrime(){
    for(int i = 2; i*i <= 1000000; i++){
        if(!ck[i]){
            for(int j = i + i; j <= 1000000; j += i){
                ck[j] = 1;
            }
        }
    }
}

int main(){
    fastio;
    makePrime();

    while(1){
        cin >> n;
        if(!n) break;
        int a = 0,b = 0;
        for(int i = 2; i <= n; i++){
            if(!ck[i] && !ck[n-i]){
                printf("%d = %d + %d\n", n,i,n-i);
                break;
            }
        }
    }
}