Crivello di Eratostene semplificato

In questo appunto di matematica è descritto un algoritmo iterativo per determinare i numeri primi fino ad un numero prefissato. Si tratta del crivello di Eratostene di Cirene, matematico dell'antica Grecia famoso anche per aver concepito il metodo trigonometrico che gli permise di calcolare la circonferenza della terra con un valore molto accurato, ricorrendo semplicemente ad osservazioni e misurazioni astronomiche.

Cosa sono i numeri primi e i numeri composti?

I numeri primi sono tutti e soli i numeri naturali che sono divisibili per uno e per se stessi.
I numeri composti sono numeri naturali che possiedono più di due divisori.
I numeri composti si possono dunque scrivere come prodotto di fattori primi grazie alla fattorizzazione o scomposizione in fattori primi, il procedimento che permette di scrivere un numero composto come prodotto di tutti i fattori primi.
Esaminiamo i seguenti numeri:

Il numero 8 è un numero pari ed è multiplo di 2 4 volte, perciò non è un numero primo.

I divisori di 8 sono: 1,2,4 e 8.
I numeri 11 e 13 sono numeri primi perché non hanno altri divisori oltre all’unità e a se stessi.
Il numero 15 ha quattro divisori: 1,3,5,15.
I numeri 11 e 13 hanno solo due divisori, l’unità e se stessi, mentre l'8 e il 15 hanno più di due divisori. I numeri come 11 e 13 sono numeri primi, i numeri come 8 e 15 sono numeri composti.

Come si fa a individuare un numero primo?

Gli strumenti che ci permettono di stabilire in maniera molto rapida se un numero è primo oppure no sono i criteri di visibilità.
Nel paragrafo precedente abbiamo detto che il numero 8 è multiplo di 2 4 volte perché è un numero pari, Abbiamo utilizzato un criterio di divisibilità: tutti i numeri pari sono divisibili per 2.
Abbiamo stabilito anche che il numero 15 non è primo, infatti, il numero ha tra 3 e 5 tra i suoi divisoti. Il numero 15 è divisibile per 3 ed è divisibile per 5.
Valgono i seguenti criteri:

• criterio di divisibilità per 5: tutti i numeri che terminano con 5 e con 0 sono divisibili per 5;
• criterio di divisibilità per 3: tutti i numeri eccetto 3, la cui somma delle cifre è un multiplo di 3 sono divisibili per 3

Applicando dunque i criteri di disabilità si può stabilire se un numero è primo oppure composto.

Per ulteriori approfondimenti sui criteri di divisibilità vedi qua

Quanti numeri primi esistono?

I numeri sono infiniti dunque anche i numeri primi sono infiniti. In molti libri di testo di aritmetica delle scuole medie è possibile reperire una tabella dei numeri primi compresi tra 1 e 1000.
E se dobbiamo identificare un numero più grande di 1000?
Il matematico greco Euclide nel libro 7 dei suoi Elementi propose già una dimostrazione sulla infinità dei numeri primi utilizzando un metodo per assurdo.
Nel 1748 il matematico Eulero propose una dimostrazione come quella fatta da Euclide utilizzando però la serie armonica. Ad ogni modo quella più semplice e breve è la dimostrazione di Euclide, riportata anche in alcuni testi scolastici.
Il numero primo più grande, conosciuto oggi, ha un numero di cifre enorme: 17 milioni di cifre.
Nel 200 a.C. Eratostene di Cirene elaboro un algoritmo in grado di ricercare i numeri compresi tra due numeri naturali, questo algoritmo è noto come Crivello di Eratostene.

Per ulteriori approfondimenti sull’infinità dei numeri primi vedi qua

Algoritmo di Eratostene perché si chiama crivello

Il crivello è uno strumento formato da un setaccio che oscilla e che ruota, dotato di maglie più o meno fini. È utilizzato in laboratorio per effettuare l’analisi ganulometrica di un campione di terreno. Una terra è un miscuglio eterogeneo di materiali, per separare il composto si utilizza questo setaccio oscillante e rotante in modo che attraverso le sue maglie passino solo i componenti delle dimensioni desiderate al fine di effettuarne una analisi. Lo scolapasta, per capirci, è una sorta di crivello.
Il crivello di Eratostene è un metodo molto antico utilizzato per trovare tutti i numeri primi minori o uguali ad un numero prefissato. Questo metodo viene insegnato anche agli alunni delle scuole elementari. Il metodo funziona proprio come un setaccio all’interno del quale vengono posizionati un blocco di numeri tra i quali bisogna individuare solo quelli primi applicando il procedimento iterativo che caratterizza l'algoritmo.

Procedura iterativa dell’algoritmo del Crivello di Eratostene

Come abbiamo detto il crivello è assimilabile a un grande setaccio all'interno del quale dobbiamo posizionare i numeri da esaminare fino a un valore massimo desiderato.
Il setaccio lascerà cadere i numeri primi e tratterrà quelli composti.
Per lavorare più facilmente i numeri possono essere ordinati in senso crescente all'interno di una griglia; si parte dal numero 1 e ci di ferma al numero massimo al di sotto del quale effettuare la ricerca. L’algoritmo funziona per eliminazioni successive, cercando di volta in volta tutti i numeri composti individuati applicando le regole in modo iterativo.
I numeri primi individuati vengono cerchiati.
Il primo numero che viene eliminato è proprio l’unità perché il numero 1 non è primo, a volte la tabella si può far iniziare direttamente dal numero 2.
Detto N il numero massimo, vediamo come si fa ad individuare tutti i numeri primi minori di N.
Ad esempio sia N=50.
Il primo numero che verrà cerchiato è sicuramente il numero 2 dopo aver eliminato l’unità.
Il secondo step prevede l’eliminazione di tutti i numeri pari. Lo step successivo prevede l’eliminazione di tutti i multipli di 3 mentre questo va cerchiato perché è primo. Ora bisogna eliminare i multipli di 5 cerchiando ovviamente il 5. Restano ancora da eliminare i multipli di 7 e cerchiare il 7.
Dopo quest’ultima eliminazione sono rimasti solo numeri primi:

Si tratta di tutti i numeri minori di 50, mentre i numeri che sono stati eliminati erano tutti i numeri composti perché avevano ciascuno più di due divisori.

Per ulteriori approfondimenti sui divisori di un numero vedi qua

Osservazioni sull’algoritmo per la ricerca dei numeri primi

In pratica la procedura iterativa dell’algoritmo prevede 3 passaggi ad ogni iterazione:

• va preso in considerazione il numero non setacciato;
• si cerchia questo numero;
• si eliminano tutti i suoi multipli

Essendo un metodo utilizzato fin dalle scuole elementari è possibile che se alcuni alunni non conoscono bene le tabelline possono trovare delle difficoltà.
In questi casi si può adottare una tecnica sostitutiva fino a quando l’alunno non avrà padronanza con la moltiplicazione.
Partendo dunque da un preciso numero primo, gli alunni possono contare spostandosi verso destra di un numero di posti pari al numero primo considerato. Così facendo la casella che viene raggiunta conterrà un suo multiplo e quindi andrà cancellato.
Ad esempio se si chiede all’alunno di cancellare i multipli di 3 da una determinata tabella, partendo da 3 dovranno eseguire tre spostamenti raggiungendo così il numero 6, ed eliminarlo, poi viene raggiunto il 9, e cancellare, e quindi il 12 e così via per tutti gli altri che vengono incontrati.
Lo stesso procedimento va ripetuto per ogni richiesta.

Per ulteriori approfondimenti sull'iterazione numerica vedi qua