(c++)백준 6588번: 골드바흐의 추측

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

6588번: 골드바흐의 추측

[풀이]

소수는 에라토스테네스의 체 알고리즘을 이용하여 풀었다.

에라토스테네스의 체 알고리즘 참고:

2020/06/18 - [백준/여러가지 문제들] - (c++)백준 1929번: 소수 구하기

(c++)백준 1929번: 소수 구하기

처음엔 매 테스트 케이스마다 n의 값이 이전 테스트 케이스의 n값보다 작으면 미리 구해둔 소수로 풀고, 크면 다시 에라토스테네스의 체 알고리즘으로 소수를 구해서 풀었더니 시간초과가 나서 애초에 n의 최댓값 - 3까지의 소수를 모두 구해놓고 풀었다.

 

#include <iostream>
#include <cstdio>//printf
using namespace std;
#define Max 1000000

int n;
int check[Max] = { 0, };//소수가 아니면 -1

//에라토스테네스의 체
void getPrime() {
	for (int i = 2; i < Max - 3; i++) {
		if (check[i] == -1)continue;
		for (int j = i + i; j <= Max - 3; j += i) {
			if (check[j] == -1)continue;
			check[j] = -1;
		}
	}
}

void getPair() {
	for (int i = 3; i <= n - 2; i++) {
		if (check[i] != -1) {
			if (check[n - i] != -1) {
				//제일 먼저 찾은 두 쌍이 차이가 가장 큰 쌍
				printf("%d = %d + %d\n", n, i, n-i);
				return;
			}
		}
	}
	printf("Goldbach's conjecture is wrong.\n");
}

void solution() {
	getPrime();
	while (1) {
		scanf("%d", &n);
		if (n == 0)break;
		getPair();
	}
}

int main() {
	solution();
	return 0;
}