에라토스테네스의 체는 주어진 범위 내에서 소수를 구할 때 유용하게 사용할 수 있는 알고리즘이다.

나는 주어진 범위 중 소수의 개수를 구하는 문제에서 시간 초과에 발목을 붙잡혔고, 이때 에라토스테네스의 체를 찾아보라는 코멘트를 듣고 찾아보게 되었다.

에라토스테네스의 체란?

에라토느테네스의 체는 소수의 배수, 즉 소수가 아닌 수를 소거하며 효율적으로 소수를 탐색하는 알고리즘이다.

앞서 설명했듯, 소수의 개수를 찾는 문제를 풀었을 당시 소수의 의미, 1과 자신만을 약수로 갖는 수라는 점에 집중하여 아래와 같은 코드를 작성했다.

def solution(n):
    answer = n-1
	
    # 2,3은 소수. 4부터 검사
    for i in range(4, n + 1):
        # 그 수의 절반만 검사해도 소수를 판별할 수 있다.
        for j in range(2, i//2+1):
            # 나눠지면 소수가 아니다
            if not(i % j):
                answer -= 1
                break
                
    return answer

이 코드는 직관적이지만 숫자가 커지고, 특히 특정 범위의 모든 소수를 구할 때는 효율적인 방버이 아니라는 단점이 존재한다.

이때 활용할 수 있는 것이 바로 에라토스테네스의 체인데, 그 원리는 다음과 같다.

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

1. 소수가 아닌 1 제거
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고 나머지 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고 나머지 3의 배수를 모두 지운다.
4. 반복

소수를 검사할 때는 자신보다 작은 수로 나눠 검사하는 것이 직관적인 방법이다. 하지만 에라토스테네스의 체는 소수인 수의 배수를 모두 지우면 지워지지 않은 수 중 가장 작은 수는 소수가 된다는 점을 활용했다.

에라토스테네스의 체는 다음과 같이 구현할 수 있다.

n = 100 # 범위
a = [False,False] + [True]*(n-1) # 체, 확실히 소수가 아닐 경우 False
primes=[]

for i in range(2,n+1):
  if a[i]: # i는 소수인가?
    primes.append(i) # i를 소수로 채택 후, i의 배수를 지운다
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

a는 그 범위의 숫자들이 확실한 소수면 False, 확실하지 않은 경우, 즉 어떤 수의 배수로써 지워질 수 있는 경우는 True로 표현한다. for문에서는 a를 통해 숫자 i가 소수인지 확인하고, True면 채택, 그리고 i의 배수를 False로 만들어 지운다.

탐색하려는 수의 범위만 확실하다면, 에라토스테네스의 체는 굉장히 강력한 알고리즘이지 않을까 하는 생각이 든다.

참고자료

• 코딩으로 수학하기