백준 9020번 C++

백준 9020번 골드바흐의 추측

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

9020번: 골드바흐의 추측

정답 코드

#include <iostream>
#include <math.h>
#define MAX 1000001             
int prime[MAX] = { 1, };
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	for (int i = 2; i <= sqrt(MAX); i++) {
		if (prime[i] != 0)
			continue;
		for (int j = i * i; j <= MAX; j += i) {
			prime[j] = 1;
		}
	}

	int n;
	cin >> n;
	int index;
	for (int x = 0; x < n; x++) {
		index = 0;
		int k;
		cin >> k;
		if (n == 0)
			break;
		bool find = false;
		for (int i = 2; i < k; i++) {
			if (i<=k-i&&prime[i] == 0 && prime[k - i] == 0) {
				index = i;
				find = true;
			
			}
		}
		cout << index << " " << k - index << '\n';

	}
}

문제 풀이

사실 골드바흐의 추측과 관련된 문제풀이는 제 블로그에도 많아서 간단히만 쓸게용
먼저 에라토스테네스의 체 알고리즘으로 소수를 구했습니다. 배열값이 0이 아니면 합성수, 0이면 소수에요
소수를 구한 뒤에는 쌍을 구해줘야 하는데
prime[i]==0이고 prime[k-i]가 0일때를 생각했습니다
i+k-i=k이기 때문입니다.