에라토스테네스의 체

에라토스테네스의 체 라고 불리는 알고리즘은 소수(Prime number)를 구하는 알고리즘이다. 여기서 소수란 '양의 약수를 두 개를 가지는 자연수' 를 의미하고 2, 3, 5, 7 ... 을 예로 들 수 있다.

 

문제를 풀다보면 소수를 대량으로 빠르게 찾아야하는 상황이 생기는데, 이 때 적합한 방법이 에라토스테네세의 체이다.

 

일반적으로 특정 숫자가 소수임을 판별하는 방법으로, 2부터 특정 숫자까지 순회하면서 특정 숫자가 나눠보고 나눠진다면 소수가 아님을 통해서 소수를 판별했다.

def is_prime(x):
    for i in range(2, x):
        if x % i == 0:
            return False
     return True

위 같이 알고리즘을 작성하는 경우, 모든 경우의 수를 다 돌면서 약수 여부를 확인하기 때문에, 시간복잡도는 O(N)일 것이다. 위의 코드는 개선 할 수 있는데, 숫자의 경우 약수가 존재 한다면 대칭을 이루는 성질이 있다. 예를 들어 6의 경우 1, 2, 3, 6 같이 양 끝을 곱했을 때 다음과 같이 대칭을 이룸을 볼 수 있다.

 

1*6,  2*3 

 

때문에 x/2 까지만 순회 해도 상관없다. 또한 특정 수의 제곱근 또한 대칭점에 근사하기에 제곱근까지만 약수의 여부를 검증하면 된다. 이렇게 한다면 O(N^(1/2))의 시간복잡드를 달성할 수 있을 것이다.

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

 

위 같은 코드는 특정 숫자가 소수인지 판별하기 좋은 코드이다. 하지만 범위 안에 있는 모든 소수 구할 때는 에라토스테네스의 체를 사용하면 좋다.

 

1부터 20까지 에라토스테네스의 체 알고리즘을 사용해서 소수를 판별해 보자.

 

기본적인 알고리즘은  2부터 시작해서 해당 숫자의 배수에 해당하는 숫자들을 모두 지워준다. 하지만 자기 자신은 지우지 않아야 한다. 또한 이미 지워진 숫자는 건너 뛴다.

 

먼저 2의 배수부터 지워보자.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

 

이후 3의 배수를 지워 보자.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

 

4는 이미 지워졌기에 건너뛴다. 이제 이 과정을 반복하면 1부터 20까지 소수를 구해낼 수 있다.

 

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

 

이를 코드로 옮겨보자.

# n까지의 소수를 구하는 함수, 
def prime_number_sieve(n):
    number_list = [1]
    for i in range(2, n+1):
        number_list.append(i)

	for i in range(2, n+1):
    	if number_list[i] == 0:         # 이미 지워진 경우 건너뛴다.
        	continue
        for j in range(i+i, n+1, i):	# 배수를 지워나간다.
            number_list[j] = 0
            
    for i in range(2, n+1):
        if number_list[i] != 0:
            print(number_list[i])