에라토스테네스의 체란? (소수 알고리즘)

❓ 에라토스테네스 체란?

지구 둘레의 길이를 처음으로 계산했던

고대 그리스의 학자 '에라토스테네스'

그는 많은 수 중 소수를 찾아내는 방법을 생각해냈습니다.

소수가 아닌 숫자를 하나씩 지워나가면서 구하는 방법이죠.

모든 수의 약수인 1을 제외하고

먼저, 소수 2를 제외한 2의 배수를 지웁니다.

그리고 소수 3을 제외한 3의 배수를 지웁니다.

계속해서 5의 배수, 7의 배수 등을 지워나가다 보면

결국 소수만 남게 됩니다.

자연수 중에서 소수만 걸러내는 이 방법이

꼭 체로 숫자를 거르는 것 같다 해서

'에라토스테네스의 체'라 합니다.