에라토스테네스의 체
ETC
2017. 3. 8. 16:46
에라토스테네스의 체는 소수를 찾는 방법이다
1부터 120까지의 수 중에서 소수를 구한다고 가정하자.
1은 소수가 아니므로 맨 처음에 제거한다.
소수인 2를 제외하고 2의 배수인 숫자들을 모두 제거한다.
(그림에서 연한 빨강으로 칠해진 부분)
다음으로 소수인 3을 제외하고 3의 배수인 숫자들을 모두 제거한다.
(그림에서 연한 초록으로 칠해진 부분)
:
이런 식으로 계속 제외하다보면 소수만 남게 된다.
(그림에서 자주색으로 칠해진 부분)
이를 이용하여 N까지의 소수를 쉽게 구할 수 있다.
이는 프로젝트 오일러 10번 문제를 푸는 데 큰 도움이 된다.