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

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 이 방법은 마치 체로 수를 걸러낸다고 하여 '에라토스테네스의 체' 라고 부른다.

풀이 과정

변수 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의 배수를 모두 지운다.

위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다