BOJ 9020 골드바흐의 추측

골드바흐의 추측이란? "2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다" 는 것이다! 이 문제는 골드바흐의 파티션, 즉 짝수 n이 주어졌을 때 짝수 n을 이루는 '두 소수'를 구하는 문제이다. 

단, 파티션이 2개 이상 주어졌을 때는 두 소수간의 차이가 가장 적은 것만을 출력한다

아래가 내가 푼 로직이다. 처음에는 그냥 for문과 if문으로 조건을 만들어서 파티션을 출력하려고 했지만너무 복잡해질 것 같아서  다른 방법을 찾았기에 이 방법을 썼다!  (속도는 확실히 좀 느리다)

 

백준 골드바흐의 추측 소스

#include <iostream>
#include <cstdio>
using namespace std;

bool prime_num[10001]; //기본값 0
void prime() //에라토스테네스의 체
// 소수 == false
// 합성수 == true 로 표시 
{
	int k = 0;
	for (int i = 2; i * i <= 10000; i++) {
		if (!prime_num[i]) { //소수일경우  
			for (int j = i * i; j <= 10000; j += i) {
				prime_num[j] = true; //합성수라고 표시 
			}
		}
	}
	prime_num[1] = true;
}


void print_partition(int n) //파티션 출력함수 
{
	if (!prime_num[n / 2]) { // n/2이 소수일경우 
		printf("%d %d", n / 2, n / 2); //n/2 값을 두개 출력해주면 된다. (두 소수의 차가 가장 적은 값)
		return;
	}
	else { //n/2이 소수가 아닐 경우 
		int m = n / 2; // 소수아님 양 옆값들 차례로 봐야한다.
		int left = m - 1; 
		int right = m + 1;

		while (1) {
			if (!prime_num[left]& !prime_num[right]) { //left와 right 모두 소수일 경우
				if (left + right == n) { //만약 left+right가 n일 경우
					printf("%d %d", left, right); //각각 출력
					return;
				}
				else if ((left + right) > n) left--; // left+right가 n보다 클 경우 감소시켜야함
                //따라서 left를 왼쪽으로 더 이동
				else if ((left + right) < n) right++; //left+right가 n보다 작을 경우 증가시켜야함
                //따라서 right을 오른쪽으로 더 이동
			}
			else { //left나 right이 소수가 아닐 경우
				if (prime_num[left]) left--; //이동
				if (prime_num[right]) right++;
			}
		}

	}
}



int main(void) {
	prime();
	int n;
	cin >> n;
	int num;
	for (int i = 0; i < n; i++) {
		cin >> num;
		print_partition(num);
		cout << endl;
	}

}

 

위 코드에서는 에라토스테네스의 체를 이용해 문제에서 주어진 n의 최댓값 까지 소수를 다 미리 표시해두었는데, n이 들어오면 바로 확인하는 방법도 있긴하다.  (근데 속도가 느려서 추천하지 않는다!!)

 

bool prime(int n) {
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) return false;
	}
	return true; 
}

 바로 이 방법이다. 입력받은 n을 이 함수에 넣으면 소수인지 아닌지를 구분해준다. 확실히 이 방법을 쓰면 bool 배열을 쓸 필요가 없기때문에 메모리는 줄지만, 속도가 너무 느리기때문에 이 방법은 쓰지 않았다. 하지만 이런식으로 에라토스테네스의 체를 이용해서 바로바로 n값이 소수인지 아닌지를 구분해줄 수 있다는 것을  알아두면 좋을 것 같다.