파이썬에서 에라토스테네스의 체

에라토스테네스의 체는 주어진 숫자 아래의 소수를 얻는 매우 일반적인 알고리즘입니다. 이 숫자는 천만 미만이어야 합니다.

이 알고리즘은 이해하기 쉽고 프로그래밍에서 자주 구현됩니다. 이 튜토리얼에서는 파이썬의 에라토스테네스의 체 알고리즘을 구현하는 방법을 보여줄 것입니다.

먼저 이 알고리즘 뒤에 있는 논리를 이해해 보겠습니다. 먼저, 숫자 2와 제공된 숫자 50 사이의 모든 숫자를 나열합니다.

그런 다음 첫 번째 소수인 2를 가져와서 그 제곱보다 크고 2로 나누어 떨어지는 모든 숫자를 표시합니다. 그런 다음 다음 소수인 3에서 동일한 작업을 반복합니다.

같은 절차를 소수 7까지 계속합니다 (7 다음 숫자의 제곱이 121이며 50보다 큽니다). 모든 숫자를 표시한 후, 표시되지 않은 값들이 50까지의 소수입니다.

아래 그림은 최종 결과를 보여줍니다.

Python에서 에라토스테네스의 체 사용

먼저 필요한 범위 목록을 만듭니다. 이 목록은 주어진 인덱스에 대해 True 또는 False로 표시됩니다.

처음에는 목록에 모든 요소가 True로 포함됩니다. 중첩 루프를 사용하여 변경하고 비 프라임 위치를 False로 표시합니다.

그런 다음 값이 여전히 True인 위치를 새 목록에 저장합니다. 이 목록에는 소수가 포함되어 있습니다.

def sieve_of_eratosthenes(val):
    max = val + 1
    lst = [True] * max
    for i in range(2, int(val ** 0.5 + 1)):
        if lst[i]:
            for j in range(i * i, max, i):
                lst[j] = False
    final = []
    for i in range(2, max):
        if lst[i]:
            final.append(i)
    return final


print(sieve_of_eratosthenes(100))

출력:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

시간 복잡도를 개선하기 위해 위의 코드를 약간 변경할 수 있습니다. 예를 들어 집합이나 사전을 사용하여 소수가 아닌 숫자를 필터링할 수 있습니다.

최종 결과는 목록으로 반환되지만 prime 및 non-prime 숫자를 True 또는 False로 표시하면서 사전이나 집합을 사용하십시오.

def sieveoferatosthenes_dict(n):
    max = n + 1
    d = dict()
    for i in range(2, max):
        d[i] = True

    for i in d:
        factors = range(i, max, i)
        for f in factors[1:]:
            d[f] = False
    lst = [i for i in d if d[i] == True]
    return lst


print(sieveoferatosthenes_dict(100))

출력:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

위의 예에서 우리는 값을 True 또는 False로 표시하기 위해 사전 d를 사용하여 소수를 필터링합니다. 최종 결과는 목록에 있습니다.