고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 이 방법은 마치 체로 수를 걸러낸다고 하여 '에라토스테네스의 체' 라고 부른다.
풀이 과정
변수 n를 선언하고 numbers[ ] 라는 배열을 (n+1)만큼의 길이로 설정하고 True로 초기화한다. 이때 숫자 0과 1은 소수가 아니므로 False로 변환한다.
에라토스테네스의 구현부분에서 0과 1은 소수가 아니라고 했으므로 for문의 범위를 2부터 설정한다. if문에서 numbers[ i ]가 True라면 i가 소수라는 의미가 된다.
이제 소수가 아닌 부분을 제거해야하는데 for문에서 i는 소수이므로 i를 제외한 i의 배수들을 변수 j에 선언하고 numbers[ j ] 에 False로 변환하여 소수가 아님을 표시한다.
코드
n = 100
numbers = [True] * (n+1) # numbers의 길이를 n+1로 설정하고 0으로 초기화
numbers[0] = numbers[1] = False # 0과 1은 소수가 아니므로 False로 변환def prime_number(): # 에라토스테네스의 체 구현
for i in range(2, int(n ** 0.5) + 1): # 2부터 n의 제곱근까지 for문 반복
if numbers[i] == True: # numbers[i]가 True일 경우 i가 소수라는 의미
for j in range(i+i, n+1, i): # i를 제외한 i의 배수를 구하는 for문
numbers[j] = False # i의 배수는 소수가 아니므로 False로 변환이때, for i in range(2, n+1)이 아닌 int(n ** 0.5) + 1을 함으로써 n의 제곱근까지를 범위로 하여 속도를 개선할 수 있다. n ** 0.5 라는 제곱근을 구하는 식에서 소수점이 나올 수 있으므로 int 함수로 소수점 이하를 버림으로 제곱근을 정수형으로 구한 뒤 +1을 하여 범위로 설정한다.
prime_number() # 에라토스테네스의 체 실행
for i in range(n+1): # numbers 모든 요소 반복하는 변수 i
if numbers[i] == True: # numbers[i]가 True라면 즉, i가 소수라면
print(i) # 소수인 i를 출력
알고리즘
-
2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
-
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
자기 자신을 제외한 2의 배수를 모두 지운다. -
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
자기 자신을 제외한 3의 배수를 모두 지운다. -
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
자기 자신을 제외한 5의 배수를 모두 지운다. -
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다
