에라토스테네스의 체: 고대 그리스의 지혜가 만든 소수 찾기 알고리즘

소수를 찾는 방법 중 가장 우아하고 효율적인 것을 꼽으라면 단연 '에라토스테네스의 체'를 들 수 있습니다. 이 알고리즘의 이름만 들어도 뭔가 특별한 것 같은 느낌이 들지 않나요? 실제로 이 방법은 그 역사와 원리가 꽤나 흥미롭습니다.

에라토스테네스, 그는 누구인가?

에라토스테네스(Eratosthenes, 기원전 276년 - 기원전 194년)는 고대 그리스의 수학자이자 지리학자, 천문학자였습니다. 그는 지구의 둘레를 놀라울 정도로 정확하게 계산한 것으로도 유명한데, 이런 다재다능한 학자가 소수를 찾는 독특한 방법을 고안해냈습니다.

체로 거르듯 소수를 찾는다

'에라토스테네스의 체'라는 이름은 이 알고리즘의 작동 방식을 아주 잘 설명해줍니다. 마치 체로 불순물을 걸러내듯, 합성수(소수가 아닌 수)를 하나씩 제거해 나가는 방식이죠.

작동 원리는 다음과 같습니다:

1. 2부터 찾고자 하는 구간의 모든 수를 나열합니다.
2. 가장 작은 수인 2를 소수로 채택하고, 2의 배수를 모두 지웁니다.
3. 남아있는 수 중 가장 작은 수를 소수로 채택하고, 그 수의 배수를 모두 지웁니다.
4. 이 과정을 반복합니다.

이렇게 하면 마지막에 남는 수들이 모두 소수가 됩니다.

파이썬으로 구현한 에라토스테네스의 체 

def sieve_of_eratosthenes(limit):
    sieve = [True] * (limit + 1)
    sieve[0:2] = [False, False]
    
    for i in range(2, int(limit**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, limit + 1, i):
                sieve[j] = False
    return [i for i, is_prime in enumerate(sieve) if is_prime]

print(len(sieve_of_eratosthenes(1000000000)))

이 코드를 실행하면 10억 이하의 모든 소수를 얻을 수 있습니다. 시간은 약 3분 50초 정도가 걸렸습니다.

왜 이렇게 효율적일까?

에라토스테네스의 체가 효율적인 이유는 각 소수의 배수를 한 번씩만 체크하기 때문입니다. 게다가 이미 지워진 수는 다시 체크하지 않아 중복 작업을 피할 수 있죠. 특히 큰 범위의 소수를 찾을 때 그 진가를 발휘합니다.

2000년도 더 된 이 알고리즘이 현대 컴퓨터 시대에도 여전히 사용되고 있다는 사실이 놀랍지 않나요? 에라토스테네스의 체는 고대 그리스 수학자의 창의성과 지혜가 시간을 초월해 빛을 발하는 훌륭한 예시입니다.

평소에 소수에 대해 깊이 생각해 볼 기회가 많지 않았는데, 이번에 에라토스테네스의 체를 알아보면서 소수의 세계에 푹 빠져들었습니다. 단순해 보이는 숫자들 사이에 이렇게 아름다운 패턴과 로직이 숨어있다는 사실이 정말 흥미진진했어요. 수학과 프로그래밍이 만나 만들어내는 이런 놀라운 순간들이, 우리가 당연하게 여기던 것들을 새로운 시각으로 바라보게 해주는 것 같습니다.