[백준] 알고리즘 C++ 6588번 - 골드바흐의 추측문제

문제

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

6588번: 골드바흐의 추측

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> prime;
bool check[1000001];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL); 
	for (long long i= 2; i <= 1000000; i++) {
		if (check[i]) continue;
		prime.push_back(i);
		for (long long j= i * i; j <= 1000000; j += i) {
			check[j] = true;
		}
	}
	while (1) {
		int n;
		cin >> n;
		if (n == 0) break;
		int n2 = n / 2;
		for (int i = 0; i < n2; i++) {
			int diff = n - prime[i];
			if (!check[diff]) {
				cout << n << " = " << prime[i] << " + " << diff;
				break;
			}
		}
		cout << "\n";
	}
}

해설

골드바흐의 증명 - 두 홀수 소수의 합으로 나타낼 수 있다.

즉 소수를 구해서 합한 값을 출력해주면된다.

 

소수는 에라토스네의 체를 사용하여 소수를 구하였습니다.

어짜피 소수는 홀수입니다. 소수를 담을 수 있는 벡터에 소수를 다 담아둡니다.

이후 N = a+b 라는 식을 만들어야하는데요,

n과 소수를 담고있는 벡터의 첫번째 요소부터 차이를 계산하면 나머지 b의 값을 찾아볼 수 있습니다.

그렇다면 check[diff]를 통해서 이 숫자가 소수인지 아닌지 판별한후 소수이면 출력하게 됩니다.

 

답은 여러개가 나올 수 있지만 우리는 제일 작은 값과 제일 큰 값부터 시작하여 비교를 합니다. 그렇다면 이 부분은 신경쓸 필요없이 바로 break를 걸어서 탈출합니다.

 

n2의 의미는 무엇이냐?

10을 계산한다고 생각해봅시다.

10 = 1 + 9

10 = 2 + 8

10 = 3 + 7

10 = 4 + 6

10 = 5 + 5

10 = 6 + 4

. . .

두 소수의 합이 중복되는 것이 있습니다. 즉 자리만 바꼈을뿐 숫자는 같은경우를 의미합니다. 시간을 조금 더 줄이기 위해서는 우리는 모든 경우를 해볼필요가 없습니다.