[백준/C & C++ ] 9020 골드바흐의 추측

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

9020번: 골드바흐의 추측

코드 (C)

#include <stdio.h>

int arr[10001] = { 0, };

int main()
{
	int n, m, a, b;

	arr[1] = 1;
	for (int i = 2; i < 10001; i++)
	{
		if (arr[i] == 1) continue;
		else for (int j = i * 2; j < 10001; j += i) arr[j] = 1;
	}

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &m);
		if (arr[m / 2] == 0) printf("%d %d\n", m / 2, m / 2);
		else
		{
			a = m / 2 -1 ;
			if (a % 2 == 0) a--;
			while (a > 0)
			{
				b = m - a;
				if (arr[a] == 0 && arr[b] == 0)
				{
					printf("%d %d\n", a, b);
					break;
				}
				a -= 2;
			}
		}
	}
	return 0;
}

코드 (C++)

#include <iostream>
using namespace std;

int arr[10001] = { 0, };

int main()
{
	int n, m,a,b;
	arr[1] = 1;

	for (int i = 2; i < 10001; i++)
	{
		if (arr[i] == 1) continue;
		else for (int j = i * 2; j < 10001; j += i) arr[j] = 1;
	}

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> m;
		if (arr[m / 2] == 0) cout << m / 2 << " " << m / 2 << "\n";
		else
		{
			a = m / 2;
			if ((m / 2) % 2 == 0) a--;
			while (a>0)
			{
				b = m - a;
				if (arr[a] == 0 && arr[b] == 0)
				{
					cout << a << " " << b << "\n";
					break;
				}
				a -= 2;
			}
		}
	}
	return 0;
}

코드설명

에라토스테네스의 체를 이용해서 미리 숫자들이 소수인지를 판별한다. 

에라토스테네스의 체 코드 설명 : https://0yeonjae2.tistory.com/m/entry/%EB%B0%B1%EC%A4%80C-1929-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0

[백준/C] 1929 소수 구하기

 

테스트케이스의 개수를 입력받고 그 수만큼 반복문을 돈다. 

문제에서 골드바흐 파티션이 여러 가지일 경우 최대한 두 소수의 차이가 작은 것을 출력하라고 했으므로,

입력받은 수가 k*2인 경우인 경우에는 바로 k를 출력한다. (k는 소수)  ex) 4 = 2 + 2 

 

입력받은 수가 위의 k*2의 경우에 해당하지 않는다는 것은 서로 다른 두 소수의 합이라는 것이다.

소수의 차이가 작아야 하므로,  점점 두 소수의 차이가 커지도록 반복문을 돌아야 한다. 

그래서 a = m/2-1로 하고, b는 m-a로 한다. 

이때 a가 짝수이면 절대로 소수가 아니다. (2가 소수이긴 하지만 2*2의 경우는 이미 위에서 구했다.) 그래서 a가 짝수라면 1을 빼서 a와 b가 모두 홀수가 되게 해준다. 

 

else 문 내의 반복문을 돌면서 a와 b가 모두 소수일 때 결과를 출력한다. 만약 그렇지 않다면 a에 2를 빼준다.

 

느낀 점

결과를 세는 곳에서 코드를 잘못 짜서 몇 번 틀렸다. 

처음에는 무한루프를 돌면서 a가 짝수인지를 고려하지 않고 코드를 짰는데, 런타임 에러 (out of bounds)가 발생했다. 그래서 a가 음수가 되는 경우가 있다는 생각이 들어서 코드를 a가 음수이면 반복문을 빠져나오도록 했다. 이렇게 고친 코드는 틀렸다고 떴다. 10000보다 작거나 같은 모든 짝수에는 골드바흐 파티션이 존재한다고 해서 뭐가 문제인지 몰랐다.

 

문제의 질문들을 찾아보다가 50, 70을 입력값으로 넣으면 출력이 안 되는 것을 알았다. 그래서 a가 짝수이면 1을 빼주는 코드를 넣어주니 통과했다. m/2가 당연히 짝수일 거라 생각한 게 문제였다.

 

반례 링크 : https://www.acmicpc.net/board/view/73014

글 읽기 - [C] 반례가 감이 안잡히네요