Sito Eratostenesa w Pythonie

powrót

Sito Eratostenesa jest algorytmem, który wykreśla ze zbioru $$[0..n]$$ liczby, które nie są pierwsze. Algorytm działa w czasie $$O(n \log(n)).$$

Został on opracowany przez greckiego matematyka, filozofa i atronoma - Eratostenesa, który żył w latach ok. 276 r. p.n.e - ok. 194 r. p.n.e.  

Strategia działania algorytmu jest bardzo prosta. Aby otrzymać zbiór wszystkich liczb pierwszych zawartych w przedziale[0..n], tworzymy listę złożoną na n + 1 elementów wypełnioną zerami. Jeśli w pod indeksem n znajduje sięwartość 0, oznacza to, że liczba n jest pierwsza, a jeśli stoi tam 0, to liczba n nie jest pierwsza. Wykreślenie liczby n z sita polega na wstawieniu wartości $$tab[n] = 1.$$ Dwie poczzątkowe komórki ustawiamy na 1, ponieważ liczby 0 i 1 nie są pierwsze. Algorytm rozpoczynamy od najmniejszej liczby pierwszej, czyli 2, kierując się do komórki o tym indeksie. Wartość tej komórki pozostawiamy niezmienioną, natomiast każdą wielokrotność dwójki ustawiamy na 1, ponieważ jest to liczba złożona (bo przecież dzieli się bez reszty przez 2). Prześledźmy przykład dla zbioru $$[2..25]$$

$$2,\ 3,\ \not 4,\ 5,\ \not 6,\ 7,\ \not 8,\ 9,\ \not {10},\ 11,\ \not {12},\ 13,\ \not {14},\ 15,\ $$

$$\not {16},\ 17,\ \not {18},\ 19,\ \not {20},\ 21,\ \not {22},\ 23,\ \not {24},\ 25$$

Teraz przechodzimy do następnej komórki w tablicy, w której wartość jest równa 0. Będzie to indeks 3 - ta komórka nie została oznaczona jako wielokrotność liczby 2, a więc jest ona pierwsza. Teraz każdą wielokrotność tej liczby wykreślamy ustawiając wartości tych komórek na 1:

$$2,\ 3,\ \not 4,\ 5,\ \not 6,\ 7,\ \not 8,\ \not 9,\ \not {10},\ 11,\ \not {12},\ 13,\ \not {14},\ \not{15},\ $$

$$\not {16},\ 17,\ \not {18},\ 19,\ \not {20},\ \not {21},\ \not {22},\ 23,\ \not {24},\ 25$$

W tym kroku nowo wykreślone liczby to: $$9,\ 15$$ oraz $$21$$.

W kolejnym kroku szukamy następnej komórki, której wartość jest równa 0. Jest nią liczba 5. Powtarzamy czynność wykreślając wielokrotności tej liczby (nowo wykreślona liczba to 25).

Zauważ, że w linijce (*) kodu przedstawionego poniżej jest zaimplementowana pętla for j in range(i*i, n+1, i):, która "każe", ustawić numer komórki do wykreślenia na wartość i*i, następnie wstawić tam wartość 1, i w końcu wykreślać co i—tą liczbę ustawiając wartość także na 1. Dlaczego przechodzimy od razu do komórki i*i? Popatrzmy na liczbę 5, która jest pierwsza. Pierwsze wykreślenie znajduje się pod komórką 5*5 = 25, ponieważ liczby 2*5, 3*5 oraz 4*5 złożone są z czynników, które zostały wcześniej wykreślone. Dodatkowo, jeśli tablica jest mniejsze niż i*i (**), to program powinien przestać się wykonywać, ponieważ nie zostanie wykreślona już żadna liczba.

W ostateczności otrzymujemy:

$$2,\ 3,\ \not 4,\ 5,\ \not 6,\ 7,\ \not 8,\ \not 9,\ \not {10},\ 11,\ \not {12},\ 13,\ \not {14},\ \not{15},\ $$

$$\not {16},\ 17,\ \not {18},\ 19,\ \not {20},\ \not {21},\ \not {22},\ 23,\ \not {24},\ \not{25}$$,

a liczby, które nie zostały wykreślone to:

$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23$$

a więc pozostały tylko liczby pierwsze.

Algorym ten stosujemy w sytuacji, gdy wymagana jest duża liczba zapytań oraz liczby te są na tyle małe, aby możliwe było utworzenie tablicy (listy) o indeksie największej z nich.

Poniżej znajduje się program w języku Python, który dla podanej wartości n przesiewa zbiór [1..n] wyznaczając liczby pierwsze.

#*****************www.algorytm.edu.pl****************
def sito(n):
    tab = []
    for i in range(n+1):
       tab.append(0) # uzupełniam listę zerami 
    tab[0] = tab[1] = 1 # liczby 0 i 1 nie są pierwsze
    i = 2 # liczba 2 jest pierwszą liczbą pierwszą
    while i*i <= n: # (**)
        if tab[i] == 0: # jeżli liczba i jest pierwsza
            for j in range(i*i, n+1, i): # (*)
                tab[j] = 1 # wykreślamy wielokrotności liczby i
        i += 1 

    return tab # zwracamy listę z sitem

# --------blok główny programu -----------

n = int(input("Podaj wielkość sita: "))

tab = sito(n)

for i in range(n + 1):
    if tab[i] == 0:
        print(i, end =' ')