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

6588번: 골드바흐의 추측 (acmicpc.net)

6588번: 골드바흐의 추측

백준 9020번의 골드바흐의 추측과 굉장히 유사한데, 달라진 점은

만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다

또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

라는 조건

 

짝수 n을 n/2-i, n/2+i로 중앙에서 가장자리 방향으로 검사했다면, 이번에는 반대로 해야할 것 같다. 

그럼 n을 2, n-2부터 시작해서 검사해나가는 코드는

while(m != 0){
        cin >> m;
        
        for(int i=2; i<m/2; i++){
            if(arr[i] && arr[m-i]){
                cout << m << " = " << i << " + " << m-i<< "\n";
                break;
            }
        }
        
    }

이렇게 하니 결과가 잘 출력된다

 

 

이제 해결해야하는 조건은 

또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

 

두 홀수 소수의 합인데, 짝수 소수는 2밖에 없으니까 2를 제외한 소수의 합으로 이루어진 합을 출력해야한다. 

 

따라서 위 코드에서 int i=3 부터 시작해서 검사해야한다.

그리고 count라는 변수를 사용해서 검사된 두 수가 있으면 count++를 하게 했다. 

count = 0이라면 검사된 두 수가 없으니  "Goldbach's conjecture is wrong." 를 출력했다. 

 

근데 이렇게 하면 

시간초과

^^

..

 

[C++] 백준 6588번 - 골드바흐의 추측 (시간초과 해결) :: 개발 블로그 (tistory.com)

[C++] 백준 6588번 - 골드바흐의 추측 (시간초과 해결)

위 글을 참고했는 데, 이 3줄을 추가해주니까 해결됨

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

위 코드를 참고해서 몇 줄 변경했는데, 

while(1){
        cin >> m;
        if(m == 0) break;

먼저 while문을 무한루프로 두고 cin을 받아서 0이면 break로 빠져나오게 바꿨다. 

 

또, 범위의 문제가 있었는데

while(1){
        cin >> m;
        if(m == 0) break;
        int count = 0;
        
        for(int i=3; i<m; i+=2){
            if(arr[i] && arr[m-i]){
                cout << m << " = " << i << " + " << m-i<< "\n";
                count++;
                break;
            }
        }
        
        if(count==0) cout << "Goldbach's conjecture is wrong.\n";
    }

for문에서 i<m/2가 아닌 i<2로 변경해주니까 맞았다

 

m은 어짜피 짝수니까 반으로 나눠도 짝수라서 i가 m/2보다 작아도 상관 없다고 한건데

그리고 어짜피 arr[i], arr[m-i]를 둘 다 검사하니까 반만 for문을 돌아도 되는데 

..

그래서 i<m/2을 하면 왜 틀렸는지 아직도 모르겠음

 

for문에서 증감은 i++ 말고 i+=2로 표현하는게 더 빠를 것 같아서 이걸로 바꿔줬다!

 

그렇게 나온 최종 코드는

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int m=1;
   
    vector<bool> arr(1000001, true);
    arr[1] = false; 
    
    for(int i=2; i*i <=1000001; i++){
        if(arr[i]==false) continue;
        for(int j = 2*i; j<=1000001; j+=i){
            if(arr[j]==false) continue;
            else arr[j] = false;
        }
    }
    
    while(1){
        cin >> m;
        if(m == 0) break;
        int count = 0;
        
        for(int i=3; i<m; i+=2){
            if(arr[i] && arr[m-i]){
                cout << m << " = " << i << " + " << m-i<< "\n";
                count++;
                break;
            }
        }
        
        if(count==0) cout << "Goldbach's conjecture is wrong.\n";
    }
    
    return 0;
}