BOJ 6588번 골드바흐의 추측

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

6588번: 골드바흐의 추측

 

두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong." 을 출력하라고 문제에 나와있는데 그럴 필요없다. 왜냐면 문제에서 주어진 n의 범위는 6 ≤ n ≤ 1000000 이고, 골드바흐의 추측은 이미 10의 18제곱 까지 증명되었기 때문이다.

​

그러므로 그냥 에라토네스의 체를 이용하여 ~n 까지의 소수의 개수를 미리 배열에 저장해두고

n = a+b 일 때 ,

n - a = b

a + b = n

이므로 n에서 저장해둔 소수를 뺀 값이 소수일 경우 출력해주면 된다.

 

#include<stdio.h>
int a[1000005] = { 1,1 }, n;
int main() 
{
	for (int i = 2; i < 1e6; i++) if (!a[i]) 
    {
			for (int j = i * 2; j < 1e6; j += i)
				a[j] = 1;
	}
	while (1) 
    {
		scanf("%d", &n);
		if (n == 0) return 0;
		bool res = false;
		for (int i = 1;; i++) if (!a[i] && !a[n - i]) 
        {
			printf("%d = %d + %d\n", n, i, n - i);
			res = true;
			break;
		}
		if (!res) printf("Goldbach's conjecture is wrong.\n");
	}
}