mercoledì 20 novembre 2013

Il Crivello di Eratostene

IL CRIVELLO DI ERATOSTENE
Eratostene(276-194 a.C.)

Fig 1.     IL CRIVELLO FINO AL NUMERO 100

Nella fig. 1 è riportato il crivello di Eratostene fino al numero 100: si  eliminano i multipli di 2( in rosso), poi quelli di 3 etc. I bianchi sono i numeri primi escludendo il numero 1.

Nel III secolo a.C., il matematico greco Eratostene di Cirene elaborò un metodo semplice per trovare tutti i numeri primi minori di un certo numero N. Consiste nello scrivere tutti i numeri interi da 2 a N e poi nell'eliminare progressivamente quelli che non servono. Disposti i numeri come in Fig.1 si parte da 2(escludendo il numero 1) e si tolgono tutti i suoi multipli (4,6,8,....). Quindi si riparte dal numero 3 e si tolgono tutti i suoi multipli che sono rimasti in tabella dopo l'eliminazione precedente. E si procede di conseguenza....
naturalmente quando i numeri crescono il procedimento diventa praticamente irresolubile.
2357111317192329313741434753
596167717379838997101103107109113127131
137139149151157163167173179181191193197199211223
227229233239241251257263269271277281293293307311
313317331337347349353359367373379383389397401409
419421431433439443449457461463467479487491499503
509521523541547557563569571577587593599601607613
617619631641643647653659661673677683691701709719
727733739743751757761769773787797809811821823827
829839853857859863877881883887907911919929937941
947953967971977983991997

Fig.2 Tavola dei numeri primi minori di 1000

Il numero primo più grande trovato da Curtis Cooper del Missouri ha 17 milioni di cifre: 3 mila pagine di testo. Esso si esprime come  (numero di Mersenne) ossia 2 moltiplicato per se stesso 57.885.161 volte, meno 1. 

Nessun commento: