Crivello di Eratostene: differenze tra le versioni

Versione delle 20:36, 4 mag 2012

Versione attuale delle 18:19, 28 giu 2025

(128 versioni intermedie di 77 utenti non mostrate)

Riga 1:

{{F|algoritmi|maggio 2017}}

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

Il '''crivello di Eratostene''' è un antico [[algoritmo]] per il calcolo dei [[numero primo|numeri primi]] fino a un certo numero prefissato. Deve il proprio nome al [[matematica|matematico]] [[Antica Grecia|greco antico]] [[Eratostene di Cirene]], che ne fu l'ideatore. È ancora utilizzato per il calcolo dei numeri primi da molti [[Programma (informatica)|programmi]] per [[computer]], per via della sua semplicità. Pur non essendo particolarmente rapido ed efficiente, infatti, è piuttosto semplice da implementare 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 ==

[[File:Sieve of Eratosthenes animation.gif|right|Animazione del crivello]]

Il procedimento è il seguente: si scrivono tutti i numeri naturali a partire da <math>2</math> fino <math>n</math> in un elenco, detto setaccio. In seguito si cancellano (setacciano) tutti i multipli del primo numero del setaccio escluso lui stesso. Si prende poi il primo numero non cancellato maggiore di <math>2</math> e si cancellano tutti i suoi multipli eccetto lui, e si ripete questa operazione fino a che il primo numero non cancellato maggiore di <math>2</math> non presenta multipli tra i numeri rimasti nell'elenco. I numeri che restano sono i [[numero primo|numeri primi]] minori o uguali a <math>n</math>.

[[Immagine:Sieve_of_Eratosthenes_animation.gif|right|Animazione del crivello]]

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

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 [[numero primo|numeri primi]] minori od uguali a ''n''.

Nel caso <math>n=50</math>, ad esempio, il procedimento di setacciatura si conclude con il numero <math>7</math> perché <math>7</math> è il massimo numero primo il cui quadrato non supera <math>50</math>; si può provare che il procedimento di setacciatura per ricercare i primi fino a un certo numero <math>n</math> termina sempre quando si raggiunge la [[radice quadrata]] di <math>n</math>. Ogni numero <math>a</math> del setaccio iniziale, contenente tutti i numeri naturali non superiori a un dato <math>n</math>, cade dal setaccio che corrisponde al più piccolo dei suoi [[fattorizzazione|divisori primi]].

È 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.

Se indichiamo con <math>p</math> il più piccolo divisore primo di <math>a</math> si ha:

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 [[fattorizzazione|divisori primi]].

:<math>a = p \cdot r \text{ con } r \ge p.</math>

Se ne deduce che <math>a = p \cdot r \ge p \cdot p = p^2</math>, da cui <math>p</math> è sempre minore o uguale alla [[radice quadrata]] di <math>a</math>.

Se indichiamo con ''p'' il più piccolo divisore primo di ''a'' si ha:

<math>a = p \times r</math> con <math>\,\!r > p</math>.

Una implementazione dell'algoritmo di Eratostene in [[Haskell (linguaggio)|Haskell]] che calcola l'n-esimo numero primo:

Se ne deduce che <math>a = p \times r \ge p \times p = p^2</math>, da cui ''p'' è sempre minore o uguale alla [[radice quadrata]] di ''a''.

<syntaxhighlight lang="haskell">

-- Una lista infinita di numeri primi prodotta

-- attraverso il metodo del crivello di Eratostene.

crivello :: [Int]

crivello = crivello' [2..]

where

crivello' :: [Int] -> [Int]

crivello' (p:ps) = p : crivello' [i | i <- ps, mod i p /= 0]

crivello' _ = undefined

-- Estrai il n-esimo numero primo.

===Esempio===

eratostene :: Int -> Int

eratostene n = crivello !! n

</syntaxhighlight>

=== Esempio ===

Per trovare tutti i numeri primi minori o uguali a [[30 (numero)|30]], si può procedere come segue:

Per trovare tutti i numeri primi minori di <math>30</math>, si può procedere come segue:

* Scrivere la lista di tutti i numeri interi da <math>2</math> a <math>30</math>:

<pre>

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

</pre>

* Cancellare dalla lista i multipli di <math>2</math>:

<pre>

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

</pre>

* Il primo numero dellaancora presente nella lista dopo il <math>2</math> è il <math>3</math>; cancellare dalla lista i rimanenti multipli di <math>3</math>:

<pre>

2 3 5 7 11 13 17 19 23 25 29

</pre>

* Il primo numero dellaancora presente nella lista dopo il <math>3</math> è il <math>5</math>; cancellare dalla lista i rimanenti multipli di <math>5</math>:

<pre>

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.

</pre>

*Il primo numero ancora presente nella lista dopo il <math>5</math> è il <math>7</math>: non essendoci più nessun multiplo di <math>7</math> nella lista, i numeri restanti sono i numeri primi cercati.

== Altri progetti ==

{{interprogetto|v=C|b_preposizionepreposizione=sul|etichetta=Il crivello di Eratostene(implementazione in C)}}

== Collegamenti esterni ==

{{Collegamenti esterni}}

{{Algebra}}

{{Mathworld|SieveofEratosthenes|Crivello di Eratostene}}

{{Teoria dei numeri}}

{{Portale|matematica}}

[[Categoria:algoritmiAlgoritmi numericiper la matematica]]

[[Categoria:Scienza ellenistica]]

[[Categoria:Numeri primi]]

[[ar:غربال إراتوستينس]]

[[bg:Решето на Ератостен]]

[[bs:Eratostenovo sito]]

[[ca:Sedàs d'Eratòstenes]]

[[cs:Eratosthenovo síto]]

[[da:Eratosthenes' si]]

[[de:Sieb des Eratosthenes]]

[[el:Κόσκινο του Ερατοσθένη]]

[[en:Sieve of Eratosthenes]]

[[eo:Kribrilo de Eratosteno]]

[[es:Criba de Eratóstenes]]

[[fa:غربال اراتوستن]]

[[fi:Eratostheneen seula]]

[[fr:Crible d'Ératosthène]]

[[he:הנפה של ארטוסתנס]]

[[hr:Eratostenovo sito]]

[[hu:Eratoszthenész szitája]]

[[id:Saringan Eratosthenes]]

[[ja:エラトステネスの篩]]

[[ka:ერატოსთენეს საცერი]]

[[ko:에라토스테네스의 체]]

[[la:Cribratum Eratosthenis]]

[[lt:Eratosteno rėtis]]

[[lv:Eratostena siets]]

[[mk:Ератостеново сито]]

[[nl:Zeef van Eratosthenes]]

[[no:Eratosthenes' sil]]

[[pl:Sito Eratostenesa]]

[[pms:Siass d'Eratòstene]]

[[pt:Crivo de Eratóstenes]]

[[ro:Ciurul lui Eratostene]]

[[ru:Решето Эратосфена]]

[[scn:Criveddu d'Eratòstini]]

[[sh:Eratostenovo sito]]

[[si:එරටොස්තනීස්ගේ පෙනේරය]]

[[simple:Sieve of Eratosthenes]]

[[sk:Eratostenovo sito]]

[[sl:Eratostenovo sito]]

[[sq:Sita e Eratostenit]]

[[sr:Ератостеново сито]]

[[sv:Eratosthenes såll]]

[[tr:Eratosten kalburu]]

[[uk:Решето Ератосфена]]

[[vi:Sàng Eratosthenes]]

[[zh:埃拉托斯特尼筛法]]