[Python/수학-정수론] 에라토스테네스의 체

에라토스테네스의 체

• 다수의 자연수에 대하여 소수 여부를 판별

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

• 이후 남아있는 수들은 모두 소수가 된다.

wikipedia.org

 

python 구현 코드

import math

n = 1000
array = [True for _ in range(n + 1)]

# 소수일 경우 True, 소수가 아닐 경우 False로 표현
for i in range(2, int(math.sqrt(n)) + 1):
    if array[i] == True:
        j = 2
        while i * j <= n: # i의 배수 모두 제거
            array[i * j] = False
            j += 1

# 남은 소수 모두 출력
for i in range(2, n + 1):
    if array[i]:
        print(i, end=' ')

• 시간복잡도

$${O(Nlg(lgN))}$$

• 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용가능
• 그러나 각 자연수에 대한 소수 여부를 판별해야 하므로 메모리가 많이 필요하다.

 

❓ 제곱근까지 확인하는 이유

$${n = a * b, n = m * m}$$

$${a * b = m * m}$$

일때, 나올 수 있는 경우의 수는 아래 세 가지만 존재한다.

a. a = m and b = m
b. a < b and b > m
c. a > b and b < m

이렇게 되면 반드시 min(a,b) <= m 이 성립하므로 m(=sqrt(n)) 까지만 수행해도 된다.

 

---

Reference

• 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유