BOJ [6588, 9020] 골드바흐의 추측

https://www.acmicpc.net/problem/6588

https://www.acmicpc.net/problem/9020

유사한 두 문제에 관한 풀이이다.

소수를 구하는 방법은 여러가지가 있다.

가장 간단한 방법으로는 임의의 숫자 n에 대하여 [1, n-1]의 범위에서 일일이 나누어보는 방법이 있겠지만

시간의 제약이 있는 알고리즘 문제에서는 사용할 수 없다.

소수를 구하는 유명한 알고리즘으로 '에라토스테네스의 체'가 있는데, 이 문제에서도 힌트로 주어져 있다.

소스 코드로 적용하기는 쉽다.

우선 bool 또는 정수형 배열 하나를 만든다. 나는 간단하게 c라고 정의했다.

우선 모든 값을 0으로 초기화하고, 숫자 n이 소수라면 c[n]의 값은 1이 된다.

for(int i = 4; i <= MAX; i += 2)
    c[i] = true;

for (int i = 3; i <= MAX; i += 2)
    if(!c[i])
        for (int j = i * 2; j <= MAX; j += i)
            c[j] = true;

MAX는 배열의 최대치로, 6588번 기준 1,000,001을 나타낸다.

2는 소수이기 때문에 첫 반복문은 4부터 시작하여 모든 짝수를 소수에서 제외한다.

두번째 반복문은 3부터 시작하여 홀수만 검사한다. c[i]값이 0이면 i의 정수배(i * 2부터)는 소수에서 제외해야 한다.

반복문이 종료되면 c 배열은 소수만 남게 된다.

이제 문제에서 원하는 출력값을 구해야 한다.

6588번은 더할 두 소수의 차가 가장 커야하고 9020은 그 반대이다.

우선 6588번의 해답을 구해본다.

임의의 숫자 n, 작은 소수 a, 큰 소수 b라고 했을 때 b-a값이 가장 큰 경우를 구해야 한다.

생각해보면 간단한데 0부터 a까지의 차이와 n부터 b까지의 차이가 같아야 a + b = n이 성립한다.

식을 조금 바꾸면 a = b - n이 된다.

즉, a와 n-b는 같다.

n이 만약 20이면 a와 b는 각각 3과 17이며 a와 n-b값이 같다.

이런 특징만 알게 되면 코드로 구성하기는 간단하다.

2를 제외한 모든 소수는 홀수이며 홀수 + 짝수는 홀수이므로 반복문에서 2는 제외하고 3부터 시작하여 2씩 증가시킨다.

for (int i = 3; i <= n; i += 2)
{
    if (!c[i] && !c[n - i])
    {
        printf("%d = %d + %d\n", n, i, n - i);
        break;
    }
}

9020번은 b-a가 가장 작아야 하는데, a와 b가 같을 때가 가장 작은 경우이다.

시작 값을 0으로 하되 짝수를 2로 나누면 짝수가 되기 때문에 i값 증가량을 1로 설정했다.

for (int i = 0; i < n / 2; i++)
{
    if (!c[n/2 - i] && !c[n/2 + i])
    {
        printf("%d %d\n", n/2 - i, n/2 + i);
        break;
    }
}