에라토스테네스의 체 (Python)

자연수 n 이하 소수의 개수를 출력하는 함수를 에라토스테네스의 체로 구현하는 방법이다.

에라토스테네스의 체는 다음과 같은 순서로 소수를 걸러낸다.

1. 현재 남아있는 수 중 가장 작은 수는 소수 (크기 순으로 정렬되어 있고 걸러지지 않았으니)
2. 이 수를 p라고 하면 2p 부터 n 까지 남아있는 p의 배수를 전부 제거한다.
3. 현재 남아있는 가장 작은 수가 $\sqrt{n}$ 보다 커지면 정지한다.

$\sqrt{n}$ 미만까지 직접 나눠서 나눠지는 숫자를 빼는 방식도 가능하지만, n이 커지면 연산 시간이 너무 늘어난다.

따라서 집합이나 리스트의 인덱스로 접근하는 것이 좋다.

 

 

- 집합(set)

def num_primes1(n) :
    nums = set(range(2, n+1))
    root_n = int(n ** (1/2))
    for i in range(2, root_n+1) :
        if i in nums :
            nums = nums - set(range(i*2, n+1, i))
    return len(nums)
    
num_primes1(100)

2부터 n까지 정수를 원소로 갖는 집합 nums를 선언한다.

2부터 $\sqrt{n}$까지의 범위를 순회하는 i가 nums 안에 있다면 i는 소수이므로,

i의 배수로 이루어진 (i*2, i*3, ... ) 집합을 nums에서 빼준다.

 

 

- 리스트(list)의 인덱스

def num_primes2(n) :
    check = [1] * (n+1)
    check[0] = check[1] = 0
    root_n = int(n ** (1/2))
    for i in range(2, root_n+1) :
        if check[i] == 1 :
            for j in range(i*2, n+1, i) :
                check[j] = 0
    return sum(check)
    
num_primes2(100)

해당 인덱스 값이 소수인지 아닌지 저장하는 리스트 check를 만든다. (check[i] = 1 이면 i는 소수, 0이면 소수가 아님)

0과 1은 소수가 아니므로 미리 0으로 바꿔준다.

마찬가지로 2부터 $\sqrt{n}$까지의 범위를 순회하는 i의 경우에 check[i] 값이 1이라면 i는 소수이므로,

i의 배수에 해당하는 인덱스 값을 가진 check의 원소들을 전부 0으로 바꿔준다.