엘리스 스쿨 코딩 테스트에서 골드바흐의 추측 문제를 접했고 해당 문제를 그대로 사용할 수는 없어, 백준의 비슷한 문제(6588. 골드바흐의 추측)를 풀이하는 포스팅을 하게 되었다.

Intuition

문제를 처음봤을 때 두 가지 옵션 중에서 무엇이 나을까 고민을 하게 되었다. 첫째는 소수를 구해놓고 그 배열 안에서 합을 만족하는 두 원소를 찾는 것이고, 둘째는 합을 만족하는 두 수를 구하고 그것들이 소수인지 판단하는 것이었다.

Approach 1

먼저 전자의 경우를 생각해봤다. 소수 배열은 에라토스테네스의 체를 활용해서 구해낼 수 있다. 그러나, 그 배열에서 합을 만족하는 두 원소를 찾는 것은 쉽지 않다. 설령 찾아냈다 하더라도 소수간에 규칙성이 없어 두 원소의 차가 가장 큰 것을 찾아내려면 결국에 모든 경우의 수를 확인하게 된다.

Approach 2

후자의 옵션으로 접근해보자. 어떤 수가 있을 때 합을 만족하는 두 수를 찾는 것은 어렵지 않다.
어떤 수가 $n$이고 두 수 중 하나를 $a$라하면 나머지 하나는 $n-a$기 때문이다.
또, 에라토스테네스의 체를 통해 미리 충분히 많은 수의 소수여부를 판단해놓은 배열을 만들어 놓는다면 소수를 판단하는 데에는 상수시간이 걸린다.

에라토스테네스의 체로 n의 최대값인 100만까지의 소수여부를 판단한 배열을 만들어 놓는다.

int main()
{
    int isPrime[1000000];
    for (int i = 0; i < 1000000; i++)
        isPrime[i] = 0;
    for (int i = 2; i * i < 1000000; i++)
    {
        if (!isPrime[i])
        {
            for (int j = i * i; j < 1000000; j += i)
            {
                isPrime[j] = 1;
            }
        }
    }
    ...

입력 n을 담을 ans변수와 두 수를 담을 변수 a,b를 선언한다.
이때, 골드바흐의 추측 내용이 두 홀수의 합으로 이루어진다는 것이기 때문에 a를 3으로 초기화시키고 b는 ans에서 3을 뺀값으로 초기화시켜준다. 마찬가지 이유로 반복문이 돌때마다 a와b는 2씩 커진다.

int ans, a, b;
scanf("%d", &ans);
while (ans)
{
	a = 3, b = ans - a;
    while (1)
    {
		...
        a += 2, b -= 2;
    }
}

남은 것은 매 반복마다 소수인지 판단하는 작업이다. 미리 만들어놓은 배열을 통해 소수인지를 판단한다. a와b 모두 소수라면 결과값을 출력후 다음값을 입력받고, 다시 위 작업을 반복한다.

int ans, a, b;
scanf("%d", &ans);
while (ans)
{
	a = 3, b = ans - a;
    while (1)
    {
		if (!isPrime[a] && !isPrime[b])
		{
			printf("%d = %d + %d\n", ans, a, b);
            scanf("%d", &ans);
			break;
		}
        a += 2, b -= 2;
    }
}

마지막 while문 안에 if부분은 while문의 condition으로 대체해주면 훨씬 코드가 간단해진다. (둘 중에 하나라도 소수가 아니면 반복문은 돌아야한다.)

Solution

#include <stdio.h>

int main()
{
    int isPrime[1000000];
    for (int i = 0; i < 1000000; i++) isPrime[i] = 0;
    for (int i = 2; i * i < 1000000; i++)
    {
        if (!isPrime[i])
        {
            for (int j = i * i; j < 1000000; j += i) isPrime[j] = 1;
        }
    }

    int ans, a, b;
    scanf("%d", &ans);
    while (ans)
    {
        a = 3, b = ans - a;
        while (isPrime[a] || isPrime[b]) a += 2, b -= 2;
        printf("%d = %d + %d\n", ans, a, b);
        scanf("%d", &ans);
    }

    return 0;
}

Complexity

• Time Complexity : 일단 에라토스테네스의 체에서 $O(n\log(\log(n)))$이 소요된다. 바깥 while문은 최대 테스트케이스 개수에 따라 $O(100000)$이 된다. 안쪽 while문의 경우 2씩 증가하여 커지면서 $O(\frac{n}{2})=O(n)$이다. 최종적으로, $O(n\log(\log n)+n)$이 된다.
• Space Complexity : 소수여부를 담을 배열 $O(n)$이 필요하다.
  $\\$
  $\\$

+) 만약 문제에서 b-a의 절댓값이 가장 작은 것을 구하는 것으로 변형된다면, a와 b를 ans의 반절부터 시작하면 된다.
ex. ans가 100이면 a와 b는 50이 된다.
#0) 100=50+50
#1) 100=49+51
#2) 100=47+53 (a,b모두 소수)

지적 및 질문 환영합니다