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.