에라토스테네스의 체
아래와 같은 과정으로 소수를 찾는 방법을 고대 그리스의 수학자 에라토스테네스(Eratosthenes)의 이름을 붙여 에라토스테네스의 체(Sieve)라 부른다.
- 우선, 수 1은 소수가 아니므로 체 밑으로 빠진다.
- 그리고, 한 수 또는 여러 수가 체 밑으로 빠지고 나면 체에 남은 자연수 중에서 가장 작은 자연수는 소수가 되므로 체에서 걸러진다.
- 다음으로, 걸러낸 한 소수의 배수는 모두 체 밑으로 빠진다.
- 이와 같은 과정을 무수히 반복하여 소수를 찾아낸다.
예를 들어 다음과 같은 차례대로 소수가 걸러진다.
- 1은 체 밑으로 빠진다.
- 남은 수 중에서 최소인 2는 소수다.
- 2의 배수는 모두 체 밑으로 빠진다.
- 남은 수 중에서 최소인 3은 소수다.
- 3의 배수는 모두 체 밑으로 빠진다.
- 남은 수 중에서 최소인 5는 소수다.
숫자로 보는 에라토스테네스의 체 with AlgeoMath
점으로 보는 에라토스테네스의 체 with AlgeoMath
게임으로 배우는 에라토스테네스의 체 with AlgeoMath
게임으로 배우는 에라토스테네스의 체 with Desmos
설명
- 중학교에서 학생이 활동하기 전에 시범을 보여주고 싶지만,
- 실제로 칠판에 적어서 하려면 시간도 오래걸리고 실수도 일어난다.
- 이를 대신하기 위해 알지오매스 블록코딩으로 만들었다.
참고
- 배움&창작(2019). 에라토스테네스의 체 with AlgeoMath.
- 배움&창작(2019). 울람 와선 with AlgeoMath.
- en.wikipedia.org/wiki/Sieve_of_Eratosthenes