에라토스테네스의 체
가장 효율적으로 소수를 찾는 고대의 방법
시작하기
'다음 단계' 버튼을 눌러 소수를 찾는 과정을 시작하세요. 1부터 120까지의 숫자 중에서 소수를 걸러내는 과정을 보여드립니다.
알고리즘 원리
1. 2부터 시작하여 현재 숫자가 지워지지 않았다면 그것은 소수입니다.
2. 발견된 소수의 모든 배수를 목록에서 지웁니다.
3. 다음 숫자로 넘어가 과정을 반복합니다.
4. √N (여기서는 약 11)까지 확인하면 모든 소수를 찾을 수 있습니다.