[Algorithm] 에라토스테네스의 체(Sieve Of Eratosthenes)

Algorithm - 에라토스테네스의 체

대수학의 아버지 알콰리즈미, 알고리즘은 그의 이름에서 유래되었다

 

알고리즘은 컴퓨터 과학의 핵심 요소이다. 검색 알고리즘 덕분에 데이터의 바다에서 원하는 것을 추출할 수 있다. 정렬 알고리즘은 난잡한 데이터들을 잘 정리하여 가공할 수 있도록 만들어준다. 그래프 알고리즘은 효율적인 연결 경로를 찾는데에 필수적이다. 알고리즘 지식은 프로그래밍과 시스템 설계에서 복잡한 문제를 해결하는데 필수적이다.

---

소수(Prime number)란 무엇인가?

What is prime number?

 

소수란 1과 자기 자신으로 밖에 나누어 떨어지지 않는 수를 의미합니다. 만약 1과 자기 자신이 아닌 수로 소수를 나눈다면 0이 아닌 나머지를 얻게 됩니다. 요소가 둘 보다 많은 수는 합성수(Composite number)라고 표현합니다.

 

생각나는 소수가 있으신가요? 2, 3, 5, 7, 11 ... 여기서 한가지 의문이 생깁니다. 그럼 1은 소수일까요 아닐까요? 결론을 이야기하자면 1은 소수가 아닙니다. 1은 요소가 자기 자신 하나밖에 없습니다. 따라서 소수도 아니고 합성수도 아닙니다.

---

에라토스테네스의 체

Sieve of Eratosthenes

 

고대 그리스 수학자 에라토스테네스는 소수를 찾는 빠른 방법을 찾아냈습니다. '체' 라는 것은 국수를 삶을 때 사용하는 그 체를 의미합니다. 즉, 에라토스테네스의 체라는 것은 수 많은 숫자들 중에서 소수를 걸러내는 방법을 의미합니다. 그 방법은 아래와 같이 매우 간단합니다.

 

a. 2부터 소수를 구하고자 하는 수를 모두 나열합니다.
b. 2는 소수이므로 빼냅니다.
c. 2를 제외한 2의 배수를 모두 제거합니다.
d. 남은 수 중에서 3은 소수이므로 빼냅니다.
e. 3을 제외한 3의 배수를 모두 제거합니다.
f. 남은 수 중에서 5는 소수이므로 빼냅니다.
g. 5를 제외한 5의 배수를 모두 제거합니다.
h. 남은 수 중에서 7은 소수이므로 빼냅니다.
i. 7을 제외한 7의 배수를 모두 제거합니다.
j. 이 과정을 반복합니다.

 

위 그림의 경우 11의 제곱이 120보다 크므로 7의 배수까지만 삭제합니다. 즉 120보다 작은 수 중에서 2, 3, 5, 7의 배수를 제거하고 남은 수는 모두 소수입니다.

 

---

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

이제 알고리즘을 파이썬 코드를 통해서 실제로 구현해보겠습니다.

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

 

Boolean 리스트를 사용하여 소수를 판단합니다. 자세한 구현 방식은 아래와 같습니다.

1. 구하려는 수의 범위 n 을 입력 받습니다. 
2. n의 크기를 가지는 리스트를 생성합니다. 이때, 모든 값을 True로 초기화합니다.
3. n의 제곱근을 계산하여 m에 대입합니다. 앞서 설명했듯이 최대 수 보다 작은 소수의 배수만 제거하면 계산이 완료되기 때문입니다.
4. 2부터 m + 1까지 순회합니다. 이때 소수를 발견하면(seive[i] == True) 배수를 삭제하기 시작합니다.
5. 자기 자신을 제외한 자신의 배수들의(i+i 부터 n까지 i의 배수로) 위치에 False를 대입합니다.
6. 다시 첫 번째 반복문으로 돌아가서 순회를 반복합니다.
7. True 값을 가지는 수의 인덱스를 출력합니다. 이는 곧 소수들을 의미합니다.

 

간단한 알고리즘인 만큼 이해도 구현도 쉽게 풀어낼 수 있습니다. 이 모든 과정을 이해했다면 베르트랑 공준(4948) 문제를 풀어보시길 바랍니다. 에라토스테네스의 체를 정복했다고 말할 수 있도록 자신이 잘 이해했는지 확인하는 시간을 가져봅시다.

---