1153 네 개의 소수

주어진 수를 4개의 소수의 합으로 나타내는 문제이다.

이 문제를 풀기위해선 다음의 가설을 알아야 한다.

"2를 제외한 모든 짝수는 두 소수의 합으로 나타낼 수 있다."

이것은 가설로 아직 증명되지 않았지만, 충분히 큰 수에서도 이 가설이 적용된다.

이것을 어떻게 사용해야 할까? 바로 4개의 소수를 2개의 소수로 바꾸면 된다.

주어진 수가 짝수라면 2, 2 를 빼버리면 다른 짝수가 될 것이다. 그 짝수는 다시 두 소수의 합으로 나타낼 수 있다!

만약 주어진 수가 홀수라면 2, 3 을 빼버리면 마찬가지로 다른 짝수가 되서 네 소수를 구할 수 있다.

단, 주어진 수가 8 미만이라면 2 2 2 2 로도 만들 수 없으므로 -1을 출력한다.

두 소수의 합은 이전에도 다뤘지만 에라토스테네스의 체를 이용해서 소수를 구하고 반복을 통해 합이 자신이 되는 두 소수를 찾아내면 된다.

소스