BOJ 6588 : 골드바흐의 추측

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/6588

 

 

어떤 숫자가 소수의 합으로 이루어져 있는지 판단해야 한다.

매번 소수 판단 함수를 사용하면, 비용이 많이 들어 time out이 나기 때문에,

주어진 n = 1000000이하의 수에 대해 모두 소수인지 미리 구해둔다.

즉, 에라토스테네스의 체를 이용하여 소수를 먼저 만든다.

 

그리고 primeNumber에는 prime을 check하여 실제 소수 값을 순서대로 적어둔다.

주어진 요구사항은, n을 만들 수 있는 방법 중 b - a가 가장 큰 값을 출력해야 하므로,

가장 작은 소수 2, 즉 primeNumber[st = 0]부터 시작하면서 n - primeNumber[st]가 소수인지 판단한다.

primeNumber[st]가 소수이고 n - primeNumber[st]가 소수면 둘이 합쳐서 n이 되므로 요구사항을 만족하게 된다.

#include <stdio.h>

int prime[1000100];
int primeNumber[1000100];
int cnt;

void makePrime()
{
	prime[1] = 1;
	for (int i = 2; i * i <= 1000000; i++)
	{
		if (!prime[i])
		{
			for (int k = i * i; k <= 1000000; k += i)
				prime[k] = 1;
		}
	}
}

int main(void)
{
	makePrime();

	for (int i = 3; i <= 1000000;i++)
		if (!prime[i]) primeNumber[cnt++] = i;

	while (1)
	{
		int st, n;

		scanf("%d", &n);

		if (n == 0) break;

		st = 0;
		while (1)
		{
			if (!prime[n - primeNumber[st]])
			{
				printf("%d = %d + %d\n", n, primeNumber[st], n - primeNumber[st]);
				break;
			}

			st++;
		}
	}

	return 0;
}

골드바흐의 추측은 현재 10¹⁸이하의 수에서는 참이므로, 위의 문제에서 예외 처리를 할 필요가 없다.