[C언어] 백준 9020 : 골드바흐의 추측

생각의 흐름

1. 소수구하는건 문제없음

2. 문제를 이해해보자면, 2보다 큰 모든 짝수는 소수 + 소수로 나타낼 수 있다는 것이다. 여기까지는 좋은데, 여기서 조건이 걸린다. 14와 같이 3 + 11, 7 + 7로 나타낼 수 있는 수는 두 소수의 차이가 가장 작은 7 + 7을 출력하는 것이다.

3. 일단 소수를 구하는 코드를 짰다. 그리고 소수 + 소수를 출력하는 것 까지 했다.

4. 문제는 차이가 작은 소수 + 소수 출력인데, 처음에는

	while (i < n)
	{
		scanf("%d", &a);
		half = a / 2;
		max = 2;
		j = 2;
		while (j <= half)
		{
			if (ft_is_prime(j) == 1)
			{
				if (max < j)
				{
					max = j;
				}
			}
			j++;
		}
		printf("%d %d\n", max, a - max);
		i++;
	}

이렇게 반으로 쪼개서, 최대값을 구하는 방법으로 진행하려했으나, 진행이 잘 되지 않았다. 여기에서 나중에 설명할 소수값을 구한다음에, a - 소수값이 소수값인가를 체크하는 부분에서 half에 가까운 수가 아니라 half에서 오히려 가장 멀어지게 된다.

5. 그래서 구글링으로 힌트를 봤다. half부터 끝까지 가는 힌트였다.

6. 나는 2부터 half까지 가서 오히려 차이가 큰 값을 출력하는데, half부터 시작하면 차이가 작은값을 출력할 수 있는 것이다.

내가 푼 코드

#include <stdio.h>

int ft_is_prime(int nb) // 소수찾기
{
	int i;
	i = 2;
	if (nb < 2)
		return (0);
	while (i <= (nb / i))
	{
		if (nb % i == 0)
			return (0);
		i++;
	}
	return (1);
}

int main()
{
	int a, n, i, half;
	scanf("%d", &n);
	i = 0;
	while (i < n)
	{
		scanf("%d", &a);
		half = a / 2;
		while (half <= a)
		{
			if (ft_is_prime(half) == 1)
			{
				if (ft_is_prime(a - half) == 1)
				break;
			}
			half++;
		}
		printf("%d %d\n", a - half, half);
		i++;
	}
}

소수를 찾고, 거기서 a - half값이 소수일 때 break를 걸어서 출력하는 방법이다. half가 증가하며 끝까지 가는 방법이기에 print할때 값을 바꾸어주었다.

다른 사람 코드들도 다 비슷한 논리이다. 하지만 소수 구하는 방법에서 차이가 있다. 나는 is_prime으로 진행했으니 일단 이걸 알아가고, 나중에 다른 방법이 필요하다면 그 때 공부해보기로 하자. 괜히 헷갈릴까봐 다른 사람 코드는 안넣을것이다.