백준 6588번 골드바흐의 추측

문제 링크입니다: https://www.acmicpc.net/problem/6588

알고리즘은 아래와 같습니다.

1. 에라토스테네스의 체를 이용하여 소수인 수를 표시하고 벡터에 홀수인 소수들만 저장시킵니다.

2. 벡터를 쭉 탐색하며 (N - 소수)도 소수인 수를 찾습니다.

3. b - a가 최대인 덧셈을 구하라고 했으니 발견하는 즉시 반복문을 탈출하고 다음 숫자에 대한 계산식을 찾습니다.

#include <iostream>

#include <vector>

using namespace std;

 

const int MAX = 1000000;

 

int minFactor[MAX];

vector<int> prime; //소수

 

//에라토스테네스의 체

void eratosthenes(void)

{

        minFactor[0] = minFactor[1] = -1;

        for (int i = 2; i < MAX; i++)

                 minFactor[i] = i;

 

        for (int i = 2; i*i < MAX; i++)

                 if (minFactor[i] == i)

                         for (int j = i * i; j < MAX; j += i)

                                 if (minFactor[j] == j)

                                          minFactor[j] = i;

 

        //홀수인 소수를 저장

        for (int i = 3; i < MAX; i++)

                 if (minFactor[i] == i)

                         prime.push_back(i);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        eratosthenes();

 

        while (1)

        {

                 int N;

                 cin >> N;

 

                 if (N == 0)

                         break;

                

                 //소수를 탐색하며

                 for(int i=0; i<prime.size(); i++)

                         //N - prime[i]도 소수인 수를 찾는다

                         if (minFactor[N - prime[i]] == N - prime[i])

                         {

                                 cout << N << " = " << prime[i] << " + " << N - prime[i] << "\n";

                                 break;

                         }

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~