imported>Pil56: sistemazione fonti, smistamento lavoro sporco e fix vari

2025-06-28T16:19:53Z

sistemazione fonti, smistamento lavoro sporco e fix vari

New page

{{F|algoritmi|maggio 2017}}
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]].

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

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

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

Se indichiamo con <math>p</math> il più piccolo divisore primo di <math>a</math> si ha:
:<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>.

Una implementazione dell'algoritmo di Eratostene in [[Haskell (linguaggio)|Haskell]] che calcola l'n-esimo numero primo:
<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.
eratostene :: Int -> Int
eratostene n = crivello !! n
</syntaxhighlight>

=== Esempio ===

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>
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 ancora 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 ancora 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
</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|preposizione=sul}}

== Collegamenti esterni ==
{{Collegamenti esterni}}

{{Algebra}}
{{Teoria dei numeri}}
{{Portale|matematica}}

[[Categoria:Algoritmi per la matematica]]
[[Categoria:Scienza ellenistica]]
[[Categoria:Numeri primi]]

Crivello di Eratostene - Revision history

imported>Pil56: sistemazione fonti, smistamento lavoro sporco e fix vari