[백준 알고리즘 c++] 문제 18. 골드 바흐의 추측 9020

문제
1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력
각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

내풀이 )

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

using namespace std;

int prime_number[10001] = { 0 };

int main()
{
	//문제
	// 1. 짝수n이 주어졌을때 소수 2개 를 출력한다.
	// 입력
	// 1. 테스트케이스 T를 입력 받는다.
	// 2. 테스트 케이스 만큼 반복문을 돌린다.
	// 2-1. 짝수 n을 입력한다.
	// 처리
	// 1. 짝수n 이 소수 2개로 어떻게 나타낼지 궁리한다.
	// 1-1. 소수들로 2차원 배열을 돌린다.
	// 1-2. 소수 2개를 합한 값이 짝수와 같으면 break걸어준다.
	// 1-2-1. 소수의 차가 가장 적은 값이 어야 한다.
	// 1-2-2. 소수 2개를 미리 받아 두고 그 두 소수의 차보다 더 적은 소수차가 나오면 업데이트되게 해서 최종적으로 그 소수를 출력하게 한다.
	// 출력
	// 1. 소수 2개를 출력한다.
	
	prime_number[1] = 1;

	for (int i = 2; i <= 10000; i++)
	{
		for (int j = i * 2; j <= 10000; j += i)
		{
			if (prime_number[j] != 1)
			{
				prime_number[j] = 1;
			}
		}
	}
	

	int T = 0;
	scanf("%d", &T);

	for (int i = 0; i < T; i++)
	{
		int n = 0;
		scanf("%d", &n);

		int prime = 10000;
		int prime2 = 0;

		for (int i = 2; i <= 10000; i++)
		{
			if (n - i < 0)
			{
				break;
			}
			
			int min = n - i; // 3
			int max = i; //13

			if (min > max)
			{
				int temp = max;
				max = min;
				min = temp;
			}

			if (prime > (max - min) && prime_number[min] == 0 && prime_number[max] == 0)
			{
				//입력값 - 소수
				prime = max - min;
				prime2 = min;

			}
		}

		if (prime2 > n - prime2)
		{
			printf("%d %d\n", n - prime2, prime2);
		}
		else
		{
			printf("%d %d\n", prime2, n - prime2);
		}
	}

	return 0;
}

문제점 : 두수의 차가 작고 범위가 작은수부터 나오게 하는 방법은 for문을 돌릴때 입력값을 2로 나눠주고 2로 나눠준 입력값을 -- 하면서 검사하는식으로 하면 작은수부터 나오게 설정할수 있음. 또한 2로 나눠줬기 때문에, i값은 두 소수의 차이가 제일 적으므로 for문을 돌면 돌수록 두 소수의 차가 멀어지게됨

다른 풀이 )

#include <stdio.h>
int main(void) {
	int t, n;
	bool num[10002];
	for (int i = 0; i <= 10001; i++) {
		num[i] = true;
	}
	num[1] = false;
	for (int i = 2; i * i <= 10001; i++) {
		if (num[i]) {
			for (int j = i * i; j <= 10001; j += i) {
				num[j] = false;
			}
		}
	}
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		//두 소수의 차이가 가장 작게 나는 경우는 n값의 절반인 경우에 해당됨 
		//n/2값을 시작으로 조사한다.
		for (int i = n / 2; i > 0; i--) {
			if (num[i] && num[n - i]) {
				printf("%d %d\n", i, n - i);
				break;
			}
		}
	}
	return 0;
}