[백준 - 1153] 네 개의 소수

자연수를 네 개의 소수 합으로 표현해야 한다. 매번 어떤 수가 소수인지 나눠 보지 않기 위해 먼저 에라토스테네스의 체로 백만 이하의 소수를 표시했다.

그다음 네 수를 한 번에 찾기보다, 남은 합을 두 소수의 합으로 만들 수 있는지 확인했다. 짝수와 홀수의 경우를 나누고, 한 쌍을 고정한 뒤 남은 값을 다시 소수 쌍으로 찾는 식이다.

이 문제에서 중요한 것은 조합을 전부 만드는 것이 아니라 소수 판정을 O(1)에 가깝게 만들고, 합을 둘씩 분리한 것이다.

문제: 1153 네 개의 소수 · 코드: GitHub에서 보기