Schermo di Eratostene

Il crivello di Eratostene è un metodo per trovare tutti i numeri primi di sotto di un certo numero naturale dato N . Lo schermo Atkin è più veloce ma più complesso.

Algoritmo

L'algoritmo procede per eliminazione: consiste nel rimuovere da una tabella di numeri interi da 2 a N tutti i multipli di un intero (diverso da se stesso).

Rimuovendo tutti questi multipli, alla fine rimarranno solo numeri interi che non sono multipli di alcun intero eccetto 1 e se stessi, e che sono quindi numeri primi.

Iniziamo cancellando i multipli di 2, poi i rimanenti multipli di 3, poi i restanti 5 multipli e così via cancellando ogni volta tutti i multipli dell'intero più piccolo rimanente.

Possiamo fermarci quando il quadrato del più piccolo intero rimanente è maggiore del più grande intero rimanente, perché in questo caso tutti i non primi sono già stati cancellati in precedenza.

Alla fine del processo, tutti i numeri interi che non sono stati barrati sono numeri primi inferiori a N.

L'animazione seguente illustra il setaccio di Eratostene per N = 120:

Nota: se un numero n è composto , allora n = n 1 n 2 , con necessariamente almeno uno dei divisori n i minore di . Questo è il motivo per cui nel setaccio sopra dove abbiamo scelto 120 poiché 121 = 11², ci fermiamo dopo aver trovato i multipli di 7. ${\ displaystyle {\ sqrt {n}}}$

Esempi di implementazione IT

Il setaccio di Eratostene può essere implementato in modo classico o ricorsivo, ma anche sotto forma di metodo pipeline .

Pseudo-codice

In una versione classica, trascriviamo l'algoritmo come segue:

Fonction Eratosthène(Limite) L = tableau de booléen de taille Limite, initialisé à Vrai L[1] = Faux Pour i de 2 à Limite Si L[i] Pour j de i*i à Limite par pas de i on peut commence à i*i car tous les multiples de i inférieurs à i*i ont déjà été rayés L[j] = Faux Fin pour Fin si Fin pour Retourner L Fin fonction

Come nell'animazione sopra, possiamo ottimizzare il codice precedente interrompendo il ciclo For i una volta i*i>Limitepoiché non entreremo più nel ciclo For j e visualizzando semplicemente gli indici di L contenenti True.

Fonction Eratosthène(Limite) L = tableau de booléen de taille Limite, initialisé à Vrai L[1] = Faux i=2 Tant que i*i≤Limite Si L[i] Pour j de i*i à Limite par pas de i on peut commence à i*i car tous les multiples de i inférieurs à i*i ont déjà été rayés L[j] = Faux Fin pour Fin si i=i+1 Fin tant que Retourner L Fin fonction

Possiamo anche evitare di controllare più volte i numeri pari e dividere il tempo di esecuzione per 2

Fonction Eratosthène(Limite) L = tableau de booléen de taille Limite, initialisé à Vrai Mettre à Faux les cases d'indice pair > 2 L[1] = Faux i=3 Tant que i*i≤Limite Si L[i] Pour j de i*i à Limite par pas de 2*i L[j] = Faux Fin pour Fin si i=i+1 Fin tant que Retourner L Fin fonction

Versione ricorsiva

Il setaccio di Eratostene è facilmente codificabile con una funzione ricorsiva, che è sufficiente chiamare inizialmente con l'array di numeri interi da 2 a N.

Ecco uno pseudo codice:

FONCTION Eratosthène( entiers ) SI premier entier au carré > dernier entier ALORS AFFICHE entiers SINON AFFICHE premier entier EXECUTE Eratosthène( tous les entiers non multiples du premier entier ) FIN SI FIN FONCTION

L'algoritmo ricorsivo ha il vantaggio di poter essere codificato su un linguaggio che non supporta una struttura dati di tipo elenco.

Versione pipeline: the Hoare Screen (1978)

L'idea è di generare ogni numero da verificare, di sottoporlo a un ordinamento a cascata, mantenendo gli interi ricevuti solo quelli primi.

Per questo ogni numero primo individuato è associato ad una posizione che trasmetterà tra i suoi successori solo quelli che non sono suoi multipli.

Questo sistema non utilizza una tabella o una lista di numeri da elaborare a priori , ma in ogni momento una stazione (cella attiva o coroutine ) per numero primo già riconosciuta .

Crible de C.A.R HOARE : Un GENERATEUR passe chaque entier de 2 à N au premier poste disponible(qu'il crée s'il n'existe pas). Pour chaque POSTE créé : * il conserve le premier entier qu'il reçoit, disons p, * puis il transmet au poste suivant (créé si besoin) tout entier reçu n non divisible par p.

In tal modo :

2 crea la posizione 2
3 passa la stazione 2 e crea la stazione 3
4 viene intercettato dalla posta 2
5 supera le stazioni 2 e 3 e crea la stazione 5
6 viene intercettato dalla posta 2
7 supera le stazioni 2, 3, 5 e crea la stazione 7
...
36 è intercettato dalla posta 2,
37 passa le stazioni 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 e crea la stazione 37 ...

Durante la crociera, questo setaccio inizia a controllare la primalità dei nuovi numeri mentre continua o completa il controllo di primalità dei numeri precedenti .

Noteremo che, a meno che non si abbia una macchina parallela con processori, questo metodo è inefficiente poiché ogni stazione attraversa un numero di interi dell'ordine di n. ${\ displaystyle {\ sqrt {n}}}$

Note e riferimenti

CAR Hoare, Comunicare i processi sequenziali , CACM 21 (1978) p. 666-677

Κόσκινον Ερατοσθένους o, Il setaccio di Eratostene. Essendo un resoconto del suo metodo per trovare tutti i numeri primi , dal Rev. Samuel Horsley, FRS, Philosophical Transactions (1683-1775), vol. 62. (1772), p. 327-347 .

Appendici

link esterno

Implementazione in C # di un'ottimizzazione del setaccio di Eratostene
[1] , applet java che simulano il setaccio di Eratostene
Il setaccio di Eratostene