백준 9020 - 골드바흐의 추측 (C++)

 

어떤 짝수가 주어졌을 때, 두 소수의 합이 이 짝수가 되는 경우 중 두 소수의 차이가 가장 적은 경우를 출력하면 된다.

예를 들면, 14의 경우 3 + 11이기도 하지만, 7 + 7이기도 하다.

이런 경우엔 7, 7을 출력하면 된다.

 

 

문제 풀이 

---

 

먼저, 에라토스테네스의 체를 이용하여 소수만을 걸러내고 시작하였다.

본인이 에라토스테네스의 체를 모른다면 아래 링크를 참고하도록 하자.

알고리즘 - 에라토스테네스의 체 (소수 판별) (tistory.com)

알고리즘 - 에라토스테네스의 체 (소수 판별)

 

 

n의 범위가 1부터 10000까지이기 때문에 먼저 10000이하의 모든 소수만을 판별해주었다.

벡터를 하나 선언한 뒤, 10001의 사이즈로 resize해주었다.

에라토스테네스의 체를 이용하여 해당 인덱스가 소수가 아니라면 값을 0으로, 소수라면 값을 -1로 저장해주었다.

 

이후, 어떠한 짝수 N이 입력된다면 이 짝수를 이루는 두 소수의 합을 구하기 위해 본인은 아래와 같은 방법을 사용하였다.

먼저 N을 반으로 나누었다.

 

이렇게 숫자를 절반으로 나누어주었다.

N이 양의 짝수이므로 N/2는 반드시 자연수이다.

 

그렇다면 먼저 N/2가 소수인지 판별을 해보자.

위에서 에라토스 테네스의 체를 이용하여, 소수 판별을 해두었기 때문에 N/2가 소수인지는 바로 알 수 있다.

 

만약 N/2가 소수라면, 그대로 N/2 N/2 를 출력해주면 된다.

N/2와 N/2는 합이 N인 두 소수이며, 그 차이가 0으로 가장 작은 차이값이기 때문이다.

 

만약, N/2가 소수가 아니라면 이제 반복문을 돌며 판별할 것이다.

먼저 한쪽의 N/2에는 1을 빼주고, 한쪽의 N/2에는 1을 더해줄 것이다.

 

이렇게 해주자. 두 수의 합이 N이 되려면 반드시 한쪽은 N/2보다 작아야 하고, 한쪽은 N/2보다 커야한다.

그렇기 떄문에 한쪽엔 1을 빼주고 한쪽엔 1을 더해주었다.

 

이 때, N/2 - 1과 N/2 + 1 이 둘 다 소수라면? 그대로 N/2 -1과 N/2 + 1을 출력해주면 된다.

 

이걸 반복문으로 계속 돌리며 확인하면 된다.

 

이렇게, 더하고 빼는 수를 1씩 올리면서 계속 검사하면 된다.

그러다가 처음으로 두 수가 모두 소수가 된다면, 그 숫자를 그대로 출력해주면 된다.

 

당연히 처음 발견된 두 소수가 그 차이가 가장 적을 수 밖에 없다.

N/2 - i 와 N/2 + i 두 수의 차이는 2i이다.

먼저 발견될수록 i가 더 작기 때문에, 2i의 값도 더 작다.

그러므로 가장 빨리 발견된 두 소수를 답으로 출력해주면 된다.

 

 

 

풀이 코드

---

std::vector<int> Nums(10001, -1);
Nums[1] = 0;

for (int i = 2; i * i <= 10000; i++)
{
    if (Nums[i] != -1)
    {
        continue;
    }

    for (int j = i + i; j <= 10000; j += i)
    {
        Nums[j] = 0;
    }
}

 

먼저 에라토스테네스의 체를 이용하여 최대 범위인 10000개의 숫자에 대해 소수를 판별해주었다.

 

int NumOfTestCase = 0;
std::cin >> NumOfTestCase;

std::vector<std::pair<int, int>> Answers(NumOfTestCase);

 

이후, 테스트케이스의 수를 입력받고, 답을 모아둘 벡터를 하나 선언하였다.

마지막에 답을 한 번에 출력할 것이기 때문이다.

for (int Case = 0; Case < NumOfTestCase; Case++)
{
    int TargetNumber = 0;
    std::cin >> TargetNumber;

    int Half = TargetNumber / 2;

    for (int i = 0; i < Half; i++)
    {
        if (Nums[Half - i] == -1 && Nums[Half + i] == -1)
        {
            Answers[Case] = { Half - i, Half + i };
            break;
        }
    }
}

 

이후, 위에서 말한 내용을 그대로 코드로 구현하면 끝이다.

먼저, 수를 입력받은 뒤 그 수의 절반을 계산한다.

 

이후, 그 나누어진 두 절반에서 한 쪽은 i를 빼고, 한 쪽엔 i를 더해주며 두 수가 모두 소수인지 판별하였다.

처음으로 발견된 두 소수를 답에 저장한 뒤, 반복문을 탈출하면 된다.

 

for (int i = 0; i < NumOfTestCase; i++)
{
    std::cout << Answers[i].first << " " << Answers[i].second << "\n";
}

return 0;

 

테스트 케이스가 모두 끝난 뒤, 답을 한 번에 출력해주면 된다.