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

🏅 Gold 2

✏️ 1차 솔루션

1. n 을 입력받으면 3부터 n/2 이하까지 돌면서 a, b 를 구하고 a, b 가 모두 소수이면 정답 출력
2. 소수 판별은 2부터 n 의 제곱근까지의 수를 돌면서 n 을 나눴을 때, n 이 나누어 떨어지지 않으면 소수로 판단

🚨 1차 trouble

시간초과ㅠㅠ

✏️ 최종 솔루션

⭐️ 소수 판별을 위해 에라토스의 체 사용

1. 에라토스의 체로 MAX까지의 모든 수에 대한 소수 판별 해주기
2. n 을 입력받으면 3부터 n/2 이하까지 돌면서 a, b 를 구하고 a, b 가 모두 소수이면 정답 출력
   ❗️ 이때 a 와 b 는 에라토스이 체로 미리 저장해둔 배열의 값이 소수를 지칭하면 소수라고 판단

📌 self feedback

소수판별을 그냥 for 문으로 써서 시간초과 발생하는 듯

✏️ 최종 code

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

bool visit[MAX]={0};

void chk() {
    for (int i=2; i*i<=MAX; i++) {
        if (visit[i]==0) {
            for (int j=i*i; j<=MAX; j+=i) {
                visit[j]=1;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    chk();
    
    while(1) {
        int n;
        cin >> n;
        if(n==0) break;
        bool exist=false;
        
        int a=-1,b=-1;
        for(int i=1;i<n/2;i++) {
            a=2*i+1;
            b=n-a;
            if(!visit[a]&&!visit[b]) {
                cout << n << " = " << a << " + " << b <<"\n";
                exist=true;
                break;
            }
        }
        
        if(!exist) cout << "Goldbach's conjecture is wrong.\n";

    }
}