Crivello di Eratostene

Il crivello di Eratostene è un antico procedimento per il calcolo delle tabelle di numeri primi fino ad un certo numero n prefissato. Deve il nome al matematico Eratostene di Cirene, che ne fu l'ideatore. È ancora utilizzato come algoritmo di calcolo dei numeri primi da molti programmi per computer; pur non essendo un algoritmo straordinariamente efficiente, infatti, è in compenso piuttosto semplice da tradurre in un qualsiasi linguaggio di programmazione.

Diverse generalizzazioni di questo metodo hanno dato vita alla teoria dei crivelli; tra di essi vi sono il crivello di Legendre e il crivello di Atkin.

Algoritmo

Animazione del crivello

Il procedimento è il seguente: si scrivono tutti i naturali a partire da 2 fino n in un elenco detto setaccio (in programmazione spesso l'elenco è implementato da un array). Poi si cancellano (setacciano) tutti i multipli del primo numero del setaccio (escluso lui stesso). Si prosegue così fino ad arrivare in fondo. I numeri che restano sono i numeri primi minori od uguali a n.

È come se si utilizzassero dei setacci a maglie via via più larghe: il primo lascia passare solo i numeri non multipli di 2, il secondo solo i non multipli di 3, e così via.

Nel caso n = 50, ad esempio, il procedimento di setacciatura si conclude con il numero 7 perché 7 è il massimo primo il cui quadrato non supera 50 e si può provare che il procedimento di setacciatura per ricercare i primi fino ad un certo numero n cessa sempre quando si supera la radice quadrata di n. Infatti ogni numero a del setaccio iniziale, contenente tutti i numeri naturali non superiori ad un dato n, cade dal setaccio che corrisponde al più piccolo dei suoi divisori primi.

Se indichiamo con p il più piccolo divisore primo di a si ha: $a=p\times r$ con $\,\!r>p$ .

Se ne deduce che $a=p\times r\geq p\times p=p^{2}$ , da cui p è sempre minore o uguale alla radice quadrata di a.

Esempio

Per trovare tutti i numeri primi minori o uguali a 30, si può procedere come segue:

Scrivere la lista di tutti i numeri interi da 2 a 30:

  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Cancellare dalla lista i multipli di 2:

  2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

Il primo numero della lista dopo il 2 è il 3; cancellare dalla lista i multipli di 3:

  2  3     5     7          11    13          17    19          23    25          29

Il primo numero della lista dopo il 3 è il 5; cancellare dalla lista i rimanenti multipli di 5:

  2  3     5     7          11    13          17    19          23                29

Il primo numero della lista dopo il 5 è il 7, ma il quadrato di 7 è 49, che è maggiore di 30 quindi
il procedimento è terminato. La lista finale consiste di tutti i numeri primi inferiori o uguali a 
30.

== In Python ==

In linguaggio Python

 
#!/usr/bin/python
# -*- coding: UTF-8 -*-
# Contribuzione realizzato da: David Alessandro Falconi Concordia.
nums=[]
prims=[]
num=input(">>> ")
for i in range(2, num+1):
	nums.append(i)
while nums != []:
	n=nums[0]
	prims.append(n)
	n=(float(n))
	for j in nums:
		if ((j % n ) == 0.0):
			nums.remove(j)
print prims

Altri progetti

Wikibooks contiene testi o manuali sul Il crivello di Eratostene(implementazione in C)
Wikiversità contiene risorse su Il crivello di Eratostene(implementazione in C)
Wikimedia Commons contiene immagini o altri file su Il crivello di Eratostene(implementazione in C)

Collegamenti esterni

(EN) Eric W. Weisstein, Crivello di Eratostene, in MathWorld, Wolfram Research.