에라토스테네스의 체: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
125.181.82.114(토론)의 18983184판 편집을 되돌림 |
|||
4번째 줄:
== 알고리즘 ==
# 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
# 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
# 자기 자신을 제외한 2의 배수를 모두 지운다.
# 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
# 자기 자신을 제외한 3의 배수를 모두 지운다.
# 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
# 자기 자신을 제외한 5의 배수를 모두 지운다.
# 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
# 자기 자신을 제외한 7의 배수를 모두 지운다.
# 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
그림의 경우, <math>11^2 > 120</math>이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.
| |||