Sito Erastotenesa
Sito Erastotenesa pozwala uzyskać zbiór liczb pierwszych. W przeciwieństwie do sprawdzania pierwszości, lepiej radzi sobie z liczeniem wielu mniejszych liczb pierwszych niż jednej dużej.
Przedstawienie algorytmu w języku Python
# sito zwraca listę z pierwszością liczb [0, n]
def sito_erastotenesa(n):
pierwsze = [True] * (n + 1)
pierwsze[0], pierwsze[1] = False, False
p = 2
while p * p <= n:
if pierwsze[p]:
# znaleziono dzielnik, zaznacz wielokrotności p jako nie-pierwsze
for i in range(p * p, n + 1, p):
pierwsze[i] = False
p += 1
return pierwsze
Wyjaśnienie algorytmu
Funkcja sito_erastotenesa generuje listę z pierwszościami liczb w zakresie od 0 do n włącznie. Algorytm działa podobnie jak sprawdzanie pierwszości, jednakże tym razem wykreślamy możliwości wielokrotności liczb. Chociaż liczba 2 jest pierwsza, bo dzieli się przez 1 i 2, tak jej wielokrotności: 2, 4, 6, 8... już nie są pierwsze, dlatego, że dzielą się przez 2.
Wykreślamy zatem wszelkie napotkane wielokrotności, poczynając od wielokrotności 2, 3, 4, 5... Elementy listy z wartością True to zatem nasze liczby pierwsze. Pierwszość liczby sprawdzamy poprzez wartość A[n], gdzie A to lista z sitem Erastotenesa, a n to nasza liczba naturalna.
Napisany przez cholewka dnia 27.11.2023 • Ostatnia zmiana: 12.01 09:23