효율적으로 소수 구하기 - 에라토스테네스의 체 (Sieve of Eratosthenes)

1. Introduction

소수는 1과 자기 자신외에는 약수를 가지지 않는 수를 의미한다.

소수를 판별하는 가장 간단한 방법은 2부터 자기자신까지의 수 (효율적으로는 $\sqrt {n}$까지)를 차례로 나눠보는 것이다.

하지만 대량의 소수를 얻어야 할 경우에도 위와 같은 방법을 쓰는 것이 최선일까?

이번 포스팅에서는 대량의 소수를 효율적으로 얻는 에라토스테네스의 체라는 방법을 소개한다.

2. Approach

에라토스테네스의 체의 기본적인 아이디어는 단일 소수판별법처럼 n에 대한 약수로 접근하는 것이 아니라, n의 배수를 기반으로 접근한다.

먼저 1은 소수가 아니므로 제외한다.

2부터 시작해서 소수를 찾으면서 합성수를 제거해 나간다. 2의 배수들은 모두 2를 약수로 가지므로 제외한다.

이제 다음으로 제외되지 않은 가장 작은 수 3을 선택하고, 3의 배수들을 제외한다.

5를 선택하고, 5의 배수들을 제외한다.

7을 선택하고, 7의 배수들을 제외한다.

이제 색칠되지 않은 칸은 100이하의 소수라고 볼 수 있다. 소수 판별법때와 마찬가지로 $\sqrt {100}$을 넘는 수는 확을 할 필요가 없기 때문이다.

3. Code

사실상 노가다나 다름 없는 이 방법은 대량의 소수를 구하는 코드에서 유용하게 사용된다. 아래 코드는 파이썬에서 에라토스테네스의 체를 이용하여 소수를 얻는 코드이다.

import math

def getPrimes(n):
    is_prime = [False, False] + [True] * (n - 1)
    max_len = int(math.sqrt(n))
    
    for i in range(2, max_len):
        if is_prime[i]:
            for j in range(2*i, n, i):
                is_prime[j] = False
    
    return [i for i in range(2, n+1) if is_prime[i]]