[BOJ] 백준 17103 골드바흐 파티션 (Swift)

문제

17103번: 골드바흐 파티션

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

www.acmicpc.net

짝수 n을 두 소수의 합으로 나타낼 수 있는 경우의 수를 구해야하는 문제입니다.
또한 순서만 다른 것은 제외해야합니다. (3 + 7, 7 + 3)

그렇다면 먼저 소수인 수들을 구해주어야겠죠?
n이 최대 1,000,000 입니다.
1,000,000 이하의 소수들을 전부 구해줍시다.

그리고 이 소수들의 합으로 n을 나타낼 수 있다면 하나씩 세어주면 되지 않을까요?

...아닙니다...

1,000,000 이하의 소수의 개수는 70,000개 이상입니다.
70,000개라고 가정하고, 70,000개에서 2개를 뽑는 경우의 수만 해도 엄청 크겠네요...
시간제한이 0.5초기 때문에 시간초과가 날 것입니다.

그렇다면 어떻게 두 소수의 합이 n인지 판단할 수 있을까요..

10을 예시로 들어보겠습니다.

감이 오시나요?

1부터 n까지 확인하면서, n = i + (n - i) 의 꼴입니다.
단순히 i와 (n - i)가 둘 다 소수이면 두 소수의 합이 n이 되겠네요!

여기서 하나더 추가하자면, 순서만 다른 것은 제외해주어야 합니다.
따라서 1부터 n이 아닌, 1부터 n / 2까지 확인해주면 됩니다.

맨 처음에는 소수들에서 2개를 뽑아서 합이 n이되면 count하는 방식으로 생각을 했었다가,
n이 1,000,000개 일때, 소수들이 너무 많아 다른 방법을 생각했던 문제입니다.

훨씬 빠른 시간내($O(n)$)에 동작하도록 구현할 수 있었습니다.