시간 초과에는 몇 가지 요인이 있습니다.

1. 에라토스테네스의 체로 소수 판정을 하셨다면, n을 받을 때마다 에라토스테네스의 체를 돌리면 안 됩니다. 맨 처음에 한 번만 하면 됩니다.
2. 2부터 차례대로 나눠보면서 소수 판정을 하셨다면, 2부터 n까지 다 나눠보면 안 됩니다. 시간 복잡도에 대해 배우면 이 방법으로 1부터 n까지의 소수를 찾을 때 O(n^2)의 시간이 걸린다는 것을 알 수 있습니다. sqrt(n)까지만 나눠도 소수 판정을 할 수 있다는 점을 활용해 보세요.
3. 합이 n인 두 소수를 찾을 때 모든 소수 쌍을 시도하면 안 됩니다. 시간 복잡도에 대해 배우면 이 방법이 O(n^2)의 시간이 걸린다는 것을 알 수 있습니다. 소수 p를 선택하면 나머지 하나는 n-p여야 한다는 점을 활용해 보세요.
4. a가 가장 작은 해 하나를 찾았다면 바로 루프를 끝내도 됩니다. 그 이후의 해는 b-a가 더 작아서 의미가 없기 때문입니다. 이래도 시간 복잡도에 어긋나지 않는가 하는 의문이 들 수 있지만, 루프가 꽤 빨리 끝나기 때문에 시간 내에 빠르게 돌아갑니다.
5. 입출력이 느리면 그것 때문에 시간 초과가 날 수 있습니다. https://www.acmicpc.net/problem/15552

그리고 n의 최댓값을 잘 보세요. 1,000,000입니다.