[BOJ] 백준 9020 골드바흐의 추측 (Swift)

문제

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

9020번: 골드바흐의 추측

풀이

이 문제는 에라스토테네스의 체 알고리즘을 사용하여 소수들을 구할 수 있습니다.
소수를 구하는 것은 쉽게 구할 수 있습니다.
이제 소수를 구한 후, 두 소수의 합이 입력받은 짝수와 같아지는 조건을 출력해주면 됩니다.
하지만, 문제의 조건중 두 소수의 차이가 가장 작은 것을 출력한다. 의 조건을 어떻게 해결해야 할지 고민을 해봐야합니다.

저는 맨 처음에는 두 소수의 합이 입력받은 짝수와 같아지는 것들을 전부 배열에 넣어준 후,
두 소수의 차이가 가장 작은 것을 기준으로 정렬하여, 그 값을 출력해주었습니다.

하지만 시간 복잡도를 더 줄일 수 있는 방법을 고민하던 중, 차이를 가장 작게 하자 라는 것에 초점을 맞추고 생각을 해보았습니다.

예를 들어 50이라는 수가 있다고 가정합시다.

차이가 가장 작으려면 25 + 25가 가장 작겠죠?
하지만 25는 소수가 아닙니다.
24 + 26
23 + 27
22 + 28 ...

이런식으로 찾아보면 가장 처음으로 조건을 만족한다면 두 소수의 차이가 가장 작은 것이 될 것입니다.

50은 (19, 31) 두 소수가 차이가 가장 작은 것 이겠네요!

에라토스테네스의 체 알고리즘을 사용하여 소수 판별을 해주고
입력받은 정수 n이 짝수이기 때문에, n / 2 부터
하나는 1씩 늘려주고, 하나는 1씩 빼주면서 두 수가 소수라면 차이가 가장 작은 소수를 구할 수 있습니다.

소스코드

후기

소수를 구하는 알고리즘은 에라토스테네스의 체 알고리즘을 떠올려서 쉽게 구할 수 있었습니다.
하지만 두 소수의 차이가 가장 작은 것을 구하는 것에 대해서 조금 더 생각해야하는 문제였던 것 같습니다.

1. 조건을 만족하는 두 소수를 전부 배열에 넣어주고, 가장 차이가 작은 것을 출력해주는 것
2. 차이가 작은 2개의 수 중 2개의 수가 소수라면 출력

이 1, 2번의 시간차이가 몇십배 정도 나는 것을 확인했습니다.