에라토스테네스의체 검색 결과
1 개의 검색 결과가 있습니다.
Algorithnm/ps 개념

[알고리즘] 에라토스테네스의 체

에라토스테네스의 체는 유명한 알고리즘입니다. 소수를 구하는 알고리즘인데요 소수란 자기자신과 1만을 가지는 정수입니다. 알고리즘: 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간..

2020. 12. 29. 17:40