Przykład implementacji sita Eratostenesa w języku Python
Linia 1. def sito podkreślnik eratostenesa podkreślnik for otwórz nawias okrągły n zamknij nawias okrągły dwukropek.
Linia 2. from math import sqrt.
Linia 3. lista podkreślnik liczb znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy.
Linia 4. lista znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy plus otwórz nawias okrągły n asterysk otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 5. max podkreślnik liczba znak równości int otwórz nawias okrągły sqrt otwórz nawias okrągły n zamknij nawias okrągły zamknij nawias okrągły.
Linia 6. for indeks in range otwórz nawias okrągły 2 przecinek max podkreślnik liczba plus 1 zamknij nawias okrągły dwukropek.
Linia 7. if lista otwórz nawias kwadratowy indeks zamknij nawias kwadratowy dwukropek.
Linia 8. for indeks podkreślnik 2 in range otwórz nawias okrągły indeks asterysk indeks przecinek n plus 1 przecinek indeks zamknij nawias okrągły dwukropek.
Linia 9. lista otwórz nawias kwadratowy indeks podkreślnik 2 zamknij nawias kwadratowy znak równości 0.
Linia 11. for element in range otwórz nawias okrągły 2 przecinek n plus 1 zamknij nawias okrągły dwukropek.
Linia 12. if lista otwórz nawias kwadratowy element zamknij nawias kwadratowy dwukropek.
Linia 13. lista podkreślnik liczb kropka append otwórz nawias okrągły element zamknij nawias okrągły.
Linia 15. print otwórz nawias okrągły lista podkreślnik liczb zamknij nawias okrągły.
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 pierwszychliczba pierwszaliczb 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:
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
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Linia 1. def sito podkreślnik eratostenesa podkreślnik for otwórz nawias okrągły n zamknij nawias okrągły dwukropek.
Linia 2. if n otwórz nawias ostrokątny 2 dwukropek.
Linia 3. return False.
Linia 4. from math import sqrt.
Linia 5. lista podkreślnik liczb znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy.
Linia 6. lista znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy plus otwórz nawias okrągły n asterysk otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 7. max podkreślnik liczba znak równości int otwórz nawias okrągły sqrt otwórz nawias okrągły n zamknij nawias okrągły zamknij nawias okrągły.
Linia 8. for indeks in range otwórz nawias okrągły 2 przecinek max podkreślnik liczba plus 1 zamknij nawias okrągły dwukropek.
Linia 9. if lista otwórz nawias kwadratowy indeks zamknij nawias kwadratowy dwukropek.
Linia 10. for indeks podkreślnik 2 in range otwórz nawias okrągły indeks asterysk indeks przecinek n plus 1 przecinek indeks zamknij nawias okrągły dwukropek.
Linia 11. lista otwórz nawias kwadratowy indeks podkreślnik 2 zamknij nawias kwadratowy znak równości 0.
Linia 13. for element in range otwórz nawias okrągły 2 przecinek n plus 1 zamknij nawias okrągły dwukropek.
Linia 14. if lista otwórz nawias kwadratowy element zamknij nawias kwadratowy dwukropek.
Linia 15. lista podkreślnik liczb kropka append otwórz nawias okrągły element zamknij nawias okrągły.
Linia 17. print otwórz nawias okrągły lista podkreślnik liczb zamknij nawias okrągły.
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 pierwsza
liczba naturalna większa od 1, mająca tylko dwa dzielniki – 1 oraz siebie samą