Baekjoon 6588 골드바흐의 추측

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

소스결과 3276 KB / 24 ms
출처 Baekjoon

언어 C++ 17

분류 수학, 정수론, 에라토스테네스의 체

 

설명

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있는지를 검증하는 프로그램을 작성한다.

 

두 홀수 소수의 합을 구하기 위해서는 일단 소수를 구해야 한다. 에라토스테네스의 체를 이용하여 소수를 구한다.

짝수인 소수는 2 단 한개밖에 없다.

출력에 있어 b - a가 가장 큰 것을 출력 한다는 말은 a가 가장 작은 수인 경우면 된다.

2개의 조건에 유의해서 문제를 해결한다.

 

알고리즘

1. 1 ~ 100만 사이의 소수를 전부 구한 후 특정 배열에 저장한다.

2. 입력 값에 대해서 3부터 순서대로 입력값을 뺀 값이 소수라면 출력 형태에 맞춰 출력한다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000000;
const int PRIMEMAX = 79498;

bool isPrime[MAX + 1];
int primeList[PRIMEMAX];
int primeCount;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	for (int i = 2; i < MAX; i++)
	{
		if (!isPrime[i])
		{
			primeList[primeCount++] = i;
			for (int j = 2; j * i < MAX; j++)
				isPrime[j * i] = true;
		}
	}

	while (true)
	{
		int tar;
		int res;

		cin >> tar;

		if (!tar)
			break;

		for (res = 1; res < primeCount && primeList[res] < tar; res++)
			if (!isPrime[tar - primeList[res]])
				break;

		if (res == primeCount || primeList[res] >= tar)
			cout << "Goldbach's conjecture is wrong.";
		else
			cout << tar << " = " << primeList[res] << " + " << tar - primeList[res] << '\n';
	}

	return 0;
}