CrivelloThis is a featured page

Il Crivello di Eratostene

Nel corso dei secoli sono stati fatti numerosi tentativi per determinare un algoritmo capace di generare solo numeri primi, e sono state fatte numerose congetture sulla primalità dei numeri appartenenti a determinate classi, alcune di queste congetture sono state in seguito smentite, altre sono ancora da dimostrare.
Il sistema più semplice per ricercare i numeri primi minori di un certo numero N è stato ideato da Eratostene di Cirene, matematico e filosofo greco vissuto nel II secolo a.c., ed è noto con il nome di CRIVELLO DI ERATOSTENE.


Si tratta di una specie di setaccio che scarta i
numeri composti e permette così di trovare i numeri primi.

Supponiamo, ad esempio, di voler trovare i numeri primi minori di 100. Scriviamo tutti i numeri compresi tra 1 e 100 in una tabella. Il numero uno viene cancellato perché non è un numero primo.

Il primo numero è 2: si cancellano tutti i multipli di 2 (2 escluso);
il primo numero che resta è 3: si cancellano tutti i multipli di 3;
il primo numero che resta è 5: si cancellano tutti i multipli di 5

poiché la radice quadrata di 100 è 10, l'ultimo numero di cui cancellare i multipli è 7; una volta cancellati i multipli di 2, 3, 5, 7, i numeri che restano sono tutti e soli i numeri primi minori di 100.

Crivello di Eratostene



No user avatar
valentina.taraddei
Latest page update: made by valentina.taraddei , May 24 2008, 2:13 AM EDT (about this update About This Update valentina.taraddei Rename - valentina.taraddei

No content added or deleted.

- complete history)
More Info: links to this page
There are no threads for this page.  Be the first to start a new thread.