BOJ (C/C++) 6588번: 골드바흐의 추측

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

6588번: 골드바흐의 추측

---

풀이

에라토스테네스의 체를 이용하여 100만까지의 소수를 구하고, 주어진 N에서 소수와 N-소수의 값이 모두 소수라면 출력했다.

---

코드

#include <stdio.h>
#include <vector>
using namespace std;

int flag[1000001];
vector <int> Isprime;

void Chae(int N);

int main() {
	int N, P;
	int i, j, cnt;

	Chae(1000000);
	cnt = Isprime.size();

	while (1) {
		scanf("%d", &N);
		if (N == 0) break;

		for (i = 0; i <= cnt / 2; i++) {

			// 소수의 i번째 원소가 소수, N - i가 소수이면
			if (!flag[N - Isprime[i]]) {
				printf("%d = %d + %d\n", N, Isprime[i], N - Isprime[i]);
				break;
			}
		}

		if (i == cnt) printf("Goldbach's conjecture is wrong.");
	}
	return 0;
}

//소수 판별 (에라토스테네스의 체)
void Chae(int N) {
	int i, j, P;

	for (i = 3; i <= N; i += 2) { // 홀수만 판별하므로 2씩 증가

		// 앞에 나왔던 (소)수의 배수가 아닌 수 = 소수
		if (!flag[i]) {
			P = i;
			Isprime.push_back(i);

			// 해당 소수의 다음 홀수인 배수, 이 또한 홀수만 판별하므로 2씩 증가
			for (j = 3 * P; j <= N; j += 2 * P) {
				if ((j%P == 0) && (!flag[j])) flag[j]++;
			}
		}
	}
}