[Algorithm/Python(파이썬)] 에라토스테네스의 체

 

에라토스테네스의 체는 수학에서 소수를 찾는 방법이다. 

고대 그리스 수학자 에라토스테네스가 발견했다. 

 

소수란?

약수가 1과 자기 자신만을 가지는 정수

 

에라토스테네스의 체 설명 그림

 

1. 2부터 구하고자 하는 구간의 모든 숫자를 나열한다.  
2. 2는 소수이므로 오른쪽에 2를 쓴다. 
3. 2를 제외한 모든 2의 배수를 지운다.
4. 남아 있는 수 중에 가장 작은 수를 오른쪽에 쓴다.
5. 그 수를 제외한 모두 그 수의 배수를 지운다. 
6. 4, 5번를 반복하면 그 구간의 모든 소수가 오른쪽에 적혀있다. 

 

처음에 에라토스테네스의 체를 알기전 아래의 코드로 소수 찾기를 구현했는데 숫자 하나 하나 for문으로 확인하니 코드의 효율성이 떨어져 시간이 초과되었다. 

# 효율성 없는 소수 찾기 코드 
def solution(n):
    num = 1
    for i in range(3, n+1):
        tf = True
        for j in range(2,i):
            if i % j == 0:
                tf = False
                break
        if tf == True:
            num += 1

    return num

 

# 에라토스테네스의 체의 방법을 이용한 소수 찾기 코드

def solution(n):
    arr = [True] * (n+1)

    for i in range(2, int(n**0.5)+1):
        for j in range(2*i, n+1, i):
            arr[j] = False
    return arr.count(True)-2
# -2는 arr[0],arr[1]을 빼주기 위해서

 

사진 출처 및 참고 링크

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전