[Python] 🐍 소수 찾기 알고리즘 (에라토스테네스의 체)

...

문제 : 1부터 입력받은 숫자 n 사이에 있는 소수를 찾아라

다음 코드는 우리가 흔히 알고 있는 소수를 찾는 방법이다.

import time
start_time = time.clock()

n = 20000
num = list(range(n+1)) # 0~50까지의 숫자를 리스트에 저장한다.
num2 = [] # 빈 리스트

for i in range(len(num)): # 리스트에 담긴 원소들을 하나하나씩 뽑을 것이다.
    for j in range(2, i):
        if i % j == 0: # 소수의 기본 연산. 2에서 자기자신-1 까지 나누어떨어지지 않는다면 소수이다.
            num[i] = 0 # 만일 소수가 아니면 해당 위치에 0을 대입하여 수정한다
    num.remove(1) # 1은 소수가 아니기 때문에 리스트에서 제거
    
for i in range(len(num)):
    if num[i] != 0:
        num2.append(num[i]) # 0이 아니라면 그 값을 새 리스트에 추가
        
end_time = time.clock()
print(end_time - start_time, '\b초')

전혀 문제없는 코드지만 그럼 n이 천 단위 만 단위가 넘어가면 어떻게 될까?

시간재는 함수를 추가해 계산해보았다.

n=5000 을 해줫더니 3초가 나왔다.
n=10000을 해줫더니 10초가 나왔다.
n=20000을 해줫더니 45초 가 나왔다
n=50000을 해줫더니 2분을 기다려도 여전히 실행상태이다 (지못미 ㅡㅡ)

이렇게 오래걸리는 코드를 가지고 먹고 살 순 없다. 문제에 제시하다시피 효율성 있는 코드를 짜자

우리는 '에라토스테네스의 체'를 사용할 것이다.

에라토스테네스의 체 란?
고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 간단하면서도 무식한 방법.
이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

- 1~n 까지 숫자를 모두 나열한다.
- 1은 소수가 아니니 삭제
- 2의 배수를 모두 삭제한다.
- 3의 배수를 모두 삭제한다.
- 4의 배수를 모두 삭제 그러나 4의배수는 2의 배수이니 넘어간다.
- 5의 배수를 모두 삭제한다.
- ....쭉쭉

이를 이행하면 결국 소수만 남게 될 것이다. 상당히 무식한 방법이지만 코딩으로 구현해보자.

import time
start_time = time.clock()

n = 210000
num = set(range(2, n+1)) # set() 자료들을 집합으로 묶는 함수다.
                         # n=10이면 {2, 3, 4, ..., 8, 9, 10} 집합이 생성된다.
                         # 집합으로 묶는 이유는 교집합, 합집합, 차집합을 이용하기 위해서다.
                         # 교집합 연산 {1, 2, 3} & {1, 7, 9} >>> {1}
                         
for i in range(2, n+1): # 1은 소수가 아니니 2서부터 시작
    if i in num: # 생성한 집합 num에 i가 들어가 있으면,
        num = set(range(2*i, n+1, i)) # 만약 i가 2라면, range(2*2, 50+1, 2) -> {4, 6, 8, 10, 12, 14, ..., 48, 50}이 된다.
                                      # 원소의 규칙을 보면 2를 제외한 2의 배수가 모두 들어가 있는 셈이다.
                                      # 차집합 연산을 이용한다. {1, 2, 3} {1} >>> {2, 3}
                                      # num에서 {4, 6, 8, 10, 12, 14, ..., 48, 50}를 차집합하면 2의 배수가 모두 삭제된다.
                                      # i가 증가해 3이면 결과적으로 3의 배수가 num 집합에서 삭제되게 된다.
                                      # i가 4, 5, 6, ... 이 되면 각각의 배수들이 삭제된다.

end_time = time.clock()
print(end_time - start_time, '\b초')