Implementacja algorytmu

Przykład implementacji sita Eratostenesa w języku Python

def sito_eratostenesa_for(n):
    from math import sqrt
    lista_liczb = []
    lista = [0] + (n * [1])
    max_liczba = int(sqrt(n))
    for indeks in range(2,max_liczba+1):
        if lista[indeks]:
            for indeks_2 in range(indeks*indeks,n+1,indeks):
                lista[indeks_2] = 0

    for element in range(2,n+1):
        if lista[element]:
            lista_liczb.append(element)

    print(lista_liczb)

Najważniejsze elementy przedstawionego kodu:

obiekt lista_liczb będzie wynikową listą liczb pierwszych w przeszukiwanym zakresie;
indeksy obiektu lista są reprezentacją zbioru liczb naturalnych z zakresu [0, n]. Początkowo wszystkie elementy traktowane są jako liczby „pierwsze” i mają wartość 1 (poza elementem o indeksie 0). Później (zgodnie z algorytmem) niektóre z nich będziemy eliminować („wykreślać”), zastępując je zerami;
zmienna max_liczba ma wartość pierwiastka kwadratowego z n, który określa górną granicę liczby, której wielokrotność wykreślamy. Zgodnie z algorytmem pierwsza pętla działa od liczby 2 do pierwiastka z liczby n (więc jako argumenty funkcji range() musimy wpisać range(2, max_liczba+1) ).

Jeśli podczas wykonywania pętli wartość elementu lista[indeks] (linia nr 7) będzie wynosić 1 (element będzie liczbą pierwszą), wówczas w wewnętrznej pętli usuwamy jej wielokrotności.

Na końcu sprawdzamy wszystkie elementy obiektu lista. Liczbami pierwszymi są indeksy elementów o wartości 1. Dopisujemy je do obiektu lista_liczb, a wynik wypisujemy.

Efekt działania programu dla liczb z zakresu od 2 do 120:

sito_eratostenesa_for(120)
[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, 101, 103, 107, 109, 113]

Problem 1

Możemy wprowadzić pewne elementy modyfikujące działanie funkcji. Spróbujmy zdefiniować funkcję sito_eratostenesa_for(n) w taki sposób, aby dla n < 2 nie próbowała ona nic obliczać, ale zwracała wartość False.

RkdszwTRhKGOy

def sito_eratostenesa_for(n):
    if n < 2:
        return False
    from math import sqrt
    lista_liczb = []
    lista = [0] + (n * [1])
    max_liczba = int(sqrt(n))
    for indeks in range(2,max_liczba+1):
        if lista[indeks]:
            for indeks_2 in range(indeks*indeks,n+1,indeks):
                lista[indeks_2] = 0

    for element in range(2,n+1):
        if lista[element]:
            lista_liczb.append(element)

    print(lista_liczb)

Słownik

liczba pierwsza

liczba naturalna większa od 1, mająca tylko dwa dzielniki – 1 oraz siebie samą

pętla zagnieżdżona

pętla, która znajduje się wewnątrz innej pętli

Wizualizacja działania - symulacja interaktywna

Strefa wyzwań

Przykład implementacji sita Eratostenesa w języku Python

Słownik