9020 골드바흐의 추측

2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다고 한다.
이 두 소수를 골드바흐의 숫자라고 하는데 주어진 문제는 짝수를 받아 그 두 소수로 나타내는것이다. 답이 여러개이면 두 수간의 차이가 가장 작은것을 출력해야 한다.

일단 소수라면 우선으로 에라토스테네스의 체를 떠올릴 수 있다.
나는 범위만큼 체를 통해 소수를 걸러내고 입력을 받아 그때그때 처리할 수 있도록 했는데 TLE가 떴다. 그냥 두 수를 고르는것은 쉽지만 두 수의 차이를 알아야 하면 O(n^2)의 시간복잡도가 걸리기 때문이다.

매 번 고를때마다 그렇게하기 때문에 내가 생각한 방법은
처음부터 각 수의 차가 작은 두 소수를 전부 만들어주고 한번에 출력하는 방법이다.
DP와 구조체를 이용해서 동전문제처럼 구현이 가능하다.
그렇게되면 매 입력을 처리하는대에 걸리는 시간은 O(1)이다.

소스