[정수론] 에라토스테네스의 체

출처 : [이것이 코딩테스트다] 책

• 에라토스테네스의 체는 O(N x loglogN) time으로 거의 사실상 선형시간에 동작할 정도로 빠르다.
• 이 분은 BC 274년에 태어난 사람이다,, 어떻게 이런걸 떠올렸을까
• 파이썬 코드로 에라토스테네스의 체를 구현해봤다.

소수 판별 (Prime Check)

• 소수 (Prime Number)란 2보다 큰 자연수 중에서, 1과 자기 자신을 제외한 수로 나누어 떨어지지 않는 자연수를 말한다.
• 다음과 같이 코드를 작성하면 O(X^1/2)에 소수를 판별할 수 있다.
  X까지 판별하지 않고, X의 제곱근까지만 체크해도 된다.

import math
def is_prime_number(x):
    if x == 1 : return False
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0: return False
    return True

print(is_prime_number(4))
print(is_prime_number(11))

결과 : False / True

에라토스테네스의 체

• 위의 코드는 O(X^1/2) 시간복잡도로 효율이 뛰어나다. 예를 들어, 판별할 수 가 1,000,000 정도 일때는 1,000 회 이하 연산으로 찾을 수 있는 것이다.

• 그런데, 하나의 수에 대해서 소수인지 판별해야 하는 경우가 아니라, 수의 범위가 주어졌을때, 그 전체 수의 범위 안에서 존재하는 모든 소수를 찾아야 하는 경우에는 어떨까?

• 에라토스테네스 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표 알고리즘이다.

• 에라토스테네스의 체 코드

import math
n = 100
array = [True for i in range(n+1)]
array[0], array[1] = False, False

for i in range(2, int(math.sqrt(n))+1):
    x = 2
    while i * x <= n:
        array[i*x] = False
        x += 1

for i in range(50,60):
    print(i,':',array[i])

결과 : 53, 59 에서 True / 나머지에서 False