Sito Eratostenesa

Sito Eratostenesa:

Algorytm Sita Eratostenesa jest pprzypisywany Eratostenesowi z Cyreny algorytm wyznaczania liczb pierwszych z zadanego przedziału [2,n].

Algorytm polega na wykreślaniu wszystkich wielokrotności jeszcze nie wykreślonych liczb z przedziału od 2 do n. Działanie rozpoczynam od liczby 2, o której wiemy, że jest liczbą pierwszą i wykreślanymy wszystkie jej wiekrotności mniejsze lub równe n. Następnie przechodzimy do kolejnej jeszcze nie wykreślonej liczby (3) i analogicznie wykreślamy jej wielokrotności, działanie to powtarzamy dla wszystkich niewykreślonych jeszcze liczb mniejszych lub równych pierwiastek z n.
Po wykonaniu tej operacji, wszystkie niewykreślone jeszcze liczby będą liczbami pierwszymi.

Przykładowa implementacje w Pythonie

# sito Eratostenesa - generowanie liczb pierwszych
 
def generuj(n):    
    T = [0]
    for i in range(1, n + 1):
        T += [1]
    i = 2
    while i <= n:
        if T[i] == 0:
            i = i + 1
        m = 2 * i
        while m <= n:
           T[m] = 0
           m = m + i
        i = i + 1
    for indeks, wartosc in enumerate(T):
        if wartosc == 1 and indeks > 1:
            print(indeks)
 
generuj(40)