[알고리즘] 소수 찾기 - 에라토스테네스의 체 by javascript
소수를 찾는 수많은 방법중에서 가장 많이 사용된다는 "에라토스테네스의 체" 라는 소수 찾기 알고리즘에 대해 알아보자. 우선 소수란 무엇일까? 소수란 간단하게 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의할 수 있다. 그럼 에라토스테네스의 체란 무엇일까? 고대 그리스 수학자 에라토스테네스가 발견했다는 소수를 찾는 방법인데, 그림과 설명을 통해 자세히 접해보자. 알고리즘 1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. (그림에서 회색 사격형으로 두른 수들이 해당한다.) 2) 2는 소수이므로 오른쪽에 2를 쓴다. 3) 자기 자신을 제외한 2의 배수를 모두 지운다. 4) 남아있는 수 가운데 3은 소수이므로 오른쪽에 쓴다. 5) 자기 자신을 제외한 3의 배수를 모두 지운다. 6) ..
2022. 3. 5.
