[알고리즘] 소수 판정과 골드바흐 파티션 - 에라토스테네스의 체 활용하기
에라토스테네스의 체는 소수를 효율적으로 찾기 위한 알고리즘이다. 1부터 N까지의 자연수 중에서 소수를 찾고 싶을 때, 다음과 같은 과정을 통해 구한다. 알고리즘 2부터 N까지의 모든 정수를 나열한다. 2는 소수이므로 제외하고, 2의 배수를 모두 지운다. 남아있는 수 중에서 가장 작은 수(3)는 소수이므로 제외하고, 3의 배수를 모두 지운다. 이 과정을 √N까지 반복하면, 남아...