Il Crivello di Eratostene: algoritmo per l’eliminazione dei multipli di numeri primi

Teoria: Il crivello di Eratostene – trovare i numeri primi eliminando i multipli dei numeri primi

Il matematico greco ERATOSTENE (275 - 194 a.C.) ha applicato un metodo inedito per trovare i numeri primi.

Si scrive la successione dei numeri naturali da 2 fino a 100, ad esempio. Si ritaglia da questa successione tutti i multipli dei numeri primi, così:

  • il numero 2 è primo, ritagliamo quindi da questa successione tutti i multipli di 2;
  • 3 è numero primo, ritagliamo quindi tutti i multipli di 3;
  • nello stesso tempo procederemo anche con 5;
  • poi seguirà 7;
  • il prossimo numero primo è 11; però, siccome 7 × 7 = 49, è inferiore a 100 e 11 × 11 = 121, che è superiore a 100, tutti i numeri rimasti dopo aver ritagliato anche i multilpli di 7 sono numeri primi;
  • I multipli di 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, ... 100
  • I multipli di 3: 6, 9, 12, 15, 18, 21, 24, 27, ... 99
  • I multipli di 5: 10, 15, 20, 25, 30, 35, 40, 45, ... 100
  • I multipli di 7: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98
  • Dopo che abbiamo eliminato i multipli di 2, 3, 5 e 7, rimangono ancora: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Che cosa è un numero primo?

Che cosa è un numero composto?

I numeri primi fino a 1.000

I numeri primi fino a 10.000

Il crivello di Eratostene

Algoritmo di Euclide

Ridurre matematica frazioni ordinarie per abbassare termini (semplificando): misure e di esempi