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

구간 내의 소수를 빠르게 찾을 수 있는 알고리즘

특징

• 구간 [1, N] 내의 모든 소수를 찾을 수 있는 알고리즘 중 가장 빠른 알고리즘
• K가 소수일 경우, K를 제외한 K의 배수(K * i, i > 1)는 소수가 아니라는 점을 이용

코드(파이썬)

def getPrimes(last) :
	#True is Prime, False is Composite
    data = [True] * last 
    data[0] = data[1] = False
    for i in range(2, int(math.sqrt(last)) + 1) :
        if data[i] == False : continue
        for j in range(2 * i, last, i) :
            data[j] = False

	#List consists of primes
    primes = []
    for i in range(last) :
        if data[i] : primes.append(i)
    return primes

• Parameter "last" : 내부 구현을 깔끔하게 하기 위해서 구간의 최댓값 + 1을 인자로 보냄
• List "data"
  • 인덱스 값에 따라 해당 인덱스 정수가 소수인지 여부를 나타내는 리스트.
  • 값이 True일 경우 소수, False일 경우 소수가 아닌수
• List "primes"
  • 소수인 값을 담는 리스트

알고리즘

• 소수가 아닌 수를 걸러내기 때문에 처음에는 모든 수를 소수(True)라고 가정함
• 반복문으로 통해서 2부터 last의 제곱근까지의 정수만큼 Boolean 값을 조사함
• 해당 값이 True인 경우, 해당하는 수 K는 소수이고 해당 수를 제외한 K의 배수는 소수가 아닌 수이다.
• 해당 값이 False인 경우, 해당하는 수 K는 이미 이전 소수의 배수임을 알 수 있다. K의 배수는 이미 이전에 나온 소수의 배수로 처리되어 있다.
• 반복문을 모두 순회한 뒤, 값이 True인 인덱스 값들이 소수의 집합

예제

• [1, 25] 사이의 소수 구하기

• 모든 수를 소수라고 가정하여 True로 할당

  [TRUE, TRUE, TRUE, TRUE, TRUE,
  TRUE, TRUE, TRUE, TRUE, TRUE,
  TRUE, TRUE, TRUE, TRUE, TRUE,
  TRUE, TRUE, TRUE, TRUE, TRUE,
  TRUE, TRUE, TRUE, TRUE, TRUE]

• 1은 먼저 소수가 아닌 수로 처리

  [FALSE, TRUE, TRUE, TRUE, TRUE,
  TRUE, TRUE, TRUE, TRUE, TRUE,
  TRUE, TRUE, TRUE, TRUE, TRUE,
  TRUE, TRUE, TRUE, TRUE, TRUE,
  TRUE, TRUE, TRUE, TRUE, TRUE]

• 2는 소수(True)이므로, 2를 제외한 2의 배수는 소수가 아님(False)

  [FALSE, TRUE, TRUE, FALSE, TRUE,
  FALSE, TRUE, FALSE, TRUE, FALSE,
  TRUE, FALSE, TRUE, FALSE, TRUE,
  FALSE, TRUE, FALSE, TRUE, FALSE,
  TRUE, FALSE, TRUE, FALSE, TRUE]

• 3도 소수(True)이므로, 3을 제외한 3의 배수는 소수가 아님(False)

  [FALSE, TRUE, TRUE, FALSE, TRUE,
  FALSE, TRUE, FALSE, FALSE, FALSE,
  TRUE, FALSE, TRUE, FALSE, FALSE,
  FALSE, TRUE, FALSE, TRUE, FALSE,
  FALSE, FALSE, TRUE, FALSE, TRUE]

• 4는 이미 소수가 아니므로(False), 4의 배수는 이미 소수가 아닌 수로 되어 있음

• 5는 소수 이므로, 5를 제외한 5의 배수는 소수가 아님

  [FALSE, TRUE, TRUE, FALSE, TRUE,
  FALSE, TRUE, FALSE, FALSE, FALSE,
  TRUE, FALSE, TRUE, FALSE, FALSE,
  FALSE, TRUE, FALSE, TRUE, FALSE,
  FALSE, FALSE, TRUE, FALSE, FALSE]

• 25의 제곱수가 5이므로, 6부터는 소수가 아닌 수가 모두 걸러져있음.

• 결과로, 소수인 수는

  2, 3, 5, 7, 11, 13, 17, 19, 23