[종만북] 에라토스테네스의 체 / 정수론 / Python 파이썬

[종만북] 에라토스테네스의 체 / 정수론 / Python 파이썬

[종만북] 에라토스테네스의 체 / 정수론 / Python 파이썬

N 까지의 모든 소수를 구하는 방법이다.

 

소수 판별을 위하여 (N ^ 0.5) 까지의 모든 수로 나눠보는 대신, (N ^ 0.5) 까지 순회하며 소수를 찾을 때마다 그 배수들을 지우는 형태로동작하기 때문에 훨씬 빠르게 수행된다.

 

 

최적화

• N 이 아니라 (N ^ 0.5) 까지만 순회.
• i 의 배수들을 모두 지울 때 2xi 에서 시작하는 것 이 아니라 (i X i) 에서 시작 / 2Xi, 3Xi 는 2 와 3의 배수를 지울때 삭제되기 때문

 

# 에라토스테네스의 체

def eratosthenes(N):
    nums = [1] * (N+1)

    nums[0] = 0
    nums[1] = 0

    sqrtn = int(N ** 0.5)

    for i in range(sqrtn+1):
        if nums[i]:
            # ( i+i = 2 * i ) 는 2의 배수를 지울 때, 3*i 는 3의 배수를 지울때 지워졌을 것이므로,
            # i * i 부터 탐색
            for j in range(i*i, N+1, i):
                nums[j] = 0
    return nums


print(eratosthenes(10))