백준 9020번 (C++)

www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

<답안>

#include <iostream>
using namespace std;
int main()
{
    int n, input;
    int temp;
    int array[10001] = {0};
    int result1, result2;
    int term;
    array[1] = -1;
    cin>>n;
    while(n-- > 0)
    {
        cin>>input;
        temp = input/2;
        for(int i=2; i<=input; i++)
        {
            for(int j=2; j*i<=input; j++)
            {
                array[i*j] = -1;
            }
        }
        for(int i=temp; i>=2; i--)
        {
            //소수를 찾은 경우
            if(array[i] == 0)
            {
                term = temp-i;
                if(array[i+2*term] == 0)
                {
                    result1 = i;
                    result2 = i+2*term;
                    break;
                }
                else
                {
                    continue;
                }
            }
        }
        cout<<result1<<" "<<result2<<"\n";
        for(int i=2; i<=temp; i++)
            array[i] = 0;
    }
    return 0;
}

 

<설명>

앞 문제들의 "에라토스테네스의 체"를 활용한 세번째 문제였다

문제를 보고 든 알고리즘은, 입력된 숫자를 2로 나눈 다음에 그 숫자를 기준으로 작은 숫자들 중에

가장 큰 소수를 먼저 찾고서, 그 소수와 2로나눈 숫자간의 간격을 더한 숫자(예 8 : 4과 3 사이 1 이므로 5)를 찾아

소수인지 판별하여 소수가 맞는 경우 두 숫자를 출력하는 식이였다

 

그러려면 2부터 입력된 숫자 input까지 에라토스테네스의 체 방법을 사용하여 소수를 찾은다음

숫자/2인 temp부터 1씩 감소시키며 소수를 비교한 다음 소수인 경우 result1으로 저장한 다음

소수 result1 + 2*간격 term 위치의 숫자가 소수인지를 판별한 다음 소수가 맞으면 result2로 저장한다

만약 소수가 아닌경우 그 다음 더 작은 숫자를 비교한다

 

최종적으로 구해진 result1 과 result2 를 출력한다