문제 출처

1. 문제설명

  • 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
  • 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하라



2. 알고리즘 설계

  • 소수 이므로, 소수를 구하는 알고리즘을 취한다.
  • 에라토스테네스의 체 사용
  • 3부터 범위 N까지 돌면서, 가장 앞의 소수와 가장 뒤의 소수가 정답



3. 로직

  • 에라토스테네스의 체
bool chk[SZ + 1];

void eratos(void)
{
	chk[1] = true;
	for (int i = 2; i <= sqrt(SZ); i++) {
		if (chk[i]) continue;
		for (int j = i * i; j <= SZ; j += i)
			chk[j] = true;
	}
}



4. 전체 코드

#include<bits/stdc++.h>
using namespace std;

const int SZ = 1000000;
bool chk[SZ + 1];

void eratos(void)
{
	chk[1] = true;
	for (int i = 2; i <= sqrt(SZ); i++) {
		if (chk[i]) continue;
		for (int j = i * i; j <= SZ; j += i)
			chk[j] = true;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	eratos();

	while (true) {
		int n; cin >> n;
		if (n == 0) break;

		bool flag = false;
		for (int i = 3; i <= n; i += 2) {
			if (!chk[i] && !chk[n - i]) {
				cout << n << " = " << i << " + " << n - i;
				flag = true;
				break;
			}
		}
		if (!flag) cout << "Goldbach's conjecture is wrong.";
		cout << '\n';
	}
}

5. 소감

  • 이 문제처럼 테스트케이스로 되어 있는 경우는
  • 최대 범위까지 한번에 구해놓는 게 편한 거 같다.