소수

[파이썬으로 배우는 알고리즘] 에라토스테네스의 체

에라토스테네스의 체란? 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법입니다. 마치 체로 치듯이 소수를 걸러낸다고 하여 '에라토스테네스의 체'라고 불립니다. 소수를 걸러내기 위해 2부터 N까지의 순서로 소수를 찾아 그 숫자의 배수들을 모두 제거하여 제거되지 않은 N까지의 모든 소수를 찾아낼 수 있습니다. 에라토스테네스의 체 적용 1) 우선 다음과 같이 1~100까지의 숫자를 나열합니다. 2) 1인 소수가 아니므로 제거합니다. 3) 2를 제외한 2의 배수를 모두 제거합니다. 4) 3을 제외한 3의 배수를 모두 제거합니다. 5) 5를 제외한 5의 배수를 모두 제거합니다. (4의 배수는 2의 배수에서 이미 제거가 되어서 지울 필요가 없음) 6) 7을 제외한 7의 배수를 모두 ..