백준 6588 - 골드바흐의 추측

문제 설명

 

 

=> 에라토네스의 체를 사용할 수 있는 지를 묻는 문제이다. 

=> 원하는 소수값을 찾기 위해서 본인과 같은 방법을 사용할 수 있다. 

=> 또 다른 방법이 있다. 

찾는 값 : 14
시작 점 : 3
14 - 3 = 11 이므로 11이 들어가 있는 index를 찾아가면 된다. 
해당 방법이 본인이 푼 방법보다 훨씬 빠르게 풀 수 있는 방법이다. 

 

 

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

vector<int> prime;
bool check[1000001];
int answer[2]={-1};

void find(int A)
{
    
    
    int IndexLimit=0;
    while(prime[IndexLimit]<=A)
    {
        ++IndexLimit;
    }
    
    for(int i=0; i<=IndexLimit; ++i)
    {
        for(int j=0; j<=IndexLimit; ++j)
        {
            if(prime[i] + prime[j] == A)
            {
                answer[0]=i;
                answer[1]=j;
                return;
            }
            else if(prime[i] +prime[j] >A)
            {
                break;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    for(long i=2; i<=1000000; ++i) //eratosthenes
    {
        if(check[i] == false)
        {
            prime.push_back(i);
            for(long long j=i*i; j<=1000000; j+=i)
            {
                check[j]=true;
            }
        }
    }
    
    int B;
    while(1)
    {
        cin>>B;
        if(B==0)break;
        else{
            find(B);
            if(answer[0] == -1)cout <<"Goldbach's conjecture is wrong."<<'\n';
            else{
                cout << B <<" = "<<prime[answer[0]]<<" + "<<prime[answer[1]]<<'\n';
                answer[0]=-1;answer[1]=-1;
            }
            
        }
    }
    return 0;
}