백준 C++ 6588번 문제 - 골드바흐의 추측

문제

골드바흐의 추측 문제는 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다고 했고, 이것을 검증하는 알고리즘을 짜는 문제다.

 

풀이

1. 에라토스 체로 소수를 구해놓았다. 배열에 소수가 아닌 수들은 모두 true로 체크를 해주었다.

2. 이제 6이상의 짝수 N을 입력받는다.

3. 에라토스 체로 구해놓은 배열을 N미만만큼 반복문으로 돈다.

4. 에라토스 체에서 홀수 소수인 A를 구하고 N에서 A를 뺀 값 B를 구한다.

5. 값 B가 소수인지 체크한다. 즉 ( A == 홀수 소수 && N - A == 홀수 소수)

6. 만약 B가 소수이면, A와 B가 모두 소수이고 이 둘의 합이 N이라는 것을 알 수 있고, 이것이 문제에서 원하는 정답이다.

 

코드

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

void che(bool arr[], int size)
{
	arr[0] = true;
	arr[1] = true;
	
	for (int i = 2; i * i < size; i++){
		if (arr[i] == true)
			continue;
		for (int j = i * i; j < size; j += i){
			arr[j] = true;
		}
	}
}

int main()
{
	bool* arr = new bool[1000001];
	che(arr, 1000001);
	int n;
	bool hasAns = false;
	while (scanf("%d", &n ) != EOF){
		if(n == 0) break;
		
		for(int i = 3; i < n; i+=2){
			if(!arr[i] && !arr[n - i] ){
				hasAns = true;
				printf("%d = %d + %d\n", n, i, n - i);
				break;
			}
		}
		
		if(!hasAns)
			printf("\nGoldbach's conjecture is wrong.\n");
	}
}

 

결과