골드바흐의 추측

https://www.acmicpc.net/problem/6588


풀이

이 문제는 시간 제한이 0.5초로 짧은 편이기 때문에 일반적인 반복문으로 소수를 판별할 시 시간 초과가 나게된다.
따라서 소수 판별에 유용한 알고리즘인 에라토스테네스의 체를 사용한다.
에라토스테네스의 체는 2부터 시작하여 2를 제외한 2의 배수를 지우고 3으로 이동하여 3를 제외한 3의 배수를 지우고
4는 2의 배수를 지울 때 지워졌음으로 넘기고 5로 이동하여 앞에 작업을 똑같이하여 소수를 찾는 방법이다.

에라토스테네스의 체를 이용한 소수 판별 외에도 반복문의 조건이나 각 언어별로 입출력이 빠른 방법을 사용해 시간을 단축 시키는 것이 해결의 중심이다.