[C언어] 백준 9020 : 골드바흐의 추측
생각의 흐름
-
소수구하는건 문제없음
-
문제를 이해해보자면, 2보다 큰 모든 짝수는 소수 + 소수로 나타낼 수 있다는 것이다. 여기까지는 좋은데, 여기서 조건이 걸린다. 14와 같이 3 + 11, 7 + 7로 나타낼 수 있는 수는 두 소수의 차이가 가장 작은 7 + 7을 출력하는 것이다.
-
일단 소수를 구하는 코드를 짰다. 그리고 소수 + 소수를 출력하는 것 까지 했다.
-
문제는 차이가 작은 소수 + 소수 출력인데, 처음에는
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에서 오히려 가장 멀어지게 된다.
-
그래서 구글링으로 힌트를 봤다. half부터 끝까지 가는 힌트였다.
-
나는 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으로 진행했으니 일단 이걸 알아가고, 나중에 다른 방법이 필요하다면 그 때 공부해보기로 하자. 괜히 헷갈릴까봐 다른 사람 코드는 안넣을것이다.
Author And Source
이 문제에 관하여([C언어] 백준 9020 : 골드바흐의 추측), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmainsain/C언어-백준-9020-골드바흐의-추측저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)