에라토스테네스의 체

에라토스테네스의 체는 가장 대표적인 소수(Prime Number) 판별 알고리즘이다. 임의의 자연수 n에 대해 그 이하의 모든 소수를 찾는 가장 간단하고 빠른 방법이다. 먼저 입력받은 수가 소수인지 판별하는 알고리즘을 작성해보자.

 

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

 

위와 같은 알고리즘의 시간복잡도는 O(N)이다. 주어진 모든 경우의 수 만큼 반복문을 돌며 약수 여부를 확인하기 때문에 매우 비효율적이다. 예를 들어 숫자 8의 경우 2 * 4 = 4 * 2와 같은 식으로 대칭을 이루기 때문이다. 더 간단하게 생각해보더라도 반복문에서 n이 8이라고 가정한다면 2에서 이미 한번 False가 반환되지만 반복이 계속되며 4에서도 한번더 False가 반환이 되기 때문에 비효율적이라고 볼 수 있다. 즉, n과 같이 소수인지 판별하고자 하는 수의 제곱근까지만 약수의 여부를 판단하면 된다. 그렇다면 시간복잡도는 O(N^(1/2))가 된다.

 

def prime(n):
    sqrt_n = int(n ** 0.5)
    for i in range(2, sqrt_n):
        if n % i == 0:
            return False
    return True

 

이렇게 하나의 수를 소수 판별 하는 것이 아닌 다수의 소수를 한 번에 판별하고자 할 때 사용하는 알고리즘이 바로 에라토스테네스의 체이다. 먼저 소수를 판별할 범위만큼 배열안에 값을 넣어준다. 1~25까지 판별해보자.

 

1. 2차원 배열에 값 초기화

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

2. 2부터 시작하여 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다.

2의 배수부터 지우는데 자기 자신은 지우지 않는다.

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

다음은 3의 배수를 지운다.

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

이미 지워진 숫자들은 건너뛰고 그 다음 배수의 숫자들을 계속해서 지워나간다.

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

남은 숫자 : 2, 3, 5, 7, 11, 13, 17, 19, 23

소수만 판별이 된 모습이다. 이것을 파이썬으로 구현해보겠다.

def prime_list(n):
	sieve = [True] * n
    
    m = int(n ** 0.5)
    for i in range(2, m + 1):
    	if sieve[i]:
        	for j in range(i+i, n, i):
            		sieve[j] = False
                
    return [i for i in range(2, n) if sieve[i]]

 

 

에라토스테네스의 체가 특정 범위 내에서 소수를 판별해야 하는 경우에는 가장 빠른 방법임에는 틀림없다. 하지만 주어진 수 하나가 소수인가에 대한 방법은 훨씬 빠르고 효율적인 방법들이 많다.