Crivello di Eratostene

Il crivello di Eratostene è un metodo per trovare i numeri primi in un intervallo di interi compreso tra 2 e n.

Come funziona

  1. Scrivo tutti i numeri tra 2 e n.
  2. Seleziono il primo numero (2)
  3. Cancello tutti i multipli di 2 dalla lista.
  4. Seleziono il secondo numero tra quelli non cancellati (3)
  5. Cancello tutti i multipli di 3 dalla lista.
  6. E così via fino a radice di n.

Al termine dell'algoritmo nella lista restano soltanto i numeri primi compresi tra 2 e n.

    Un esempio pratico

    Scrivo i numeri da 1 a 100

    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
    31 32 33 34 35 36 37 38 39 40
    41 42 43 44 45 46 47 48 49 50
    51 52 53 54 55 56 57 58 59 60
    61 62 63 64 65 66 67 68 69 70
    71 72 73 74 75 76 77 78 79 80
    81 82 83 84 85 86 87 88 89 90
    91 92 93 94 95 96 97 98 99 100

    Per trovare i primi da 1 a 100 mi basta eliminare i multipli degli interi da 1 a radice(100) ossia da 1 a 10.

    Seleziono 2 ed elimino i multipli di 2

    2 3 5 7 9
    11 13 15 17 19
    21 23 25 27 29
    31 33 35 37 39
    41 43 45 47 49
    51 53 55 57 59
    61 63 65 67 69
    71 73 75 77 79
    81 83 85 87 89
    91 93 95 97 99

    Poi seleziono 3 ed elimino tutti i multipli di 3 che si trovano ancora nella tabella.

    2 3 5 7
    11 13 17 19
    23 25 29
    31 35 37
    41 43 47 49
    53 55 59
    61 65 67
    71 73 77 79
    83 85 89
    91 95 97

    Il numero successivo è 5. Lo seleziono ed elimino i multipli di 5.

    2 3 5 7
    11 13 17 19
    23 29
    31 37
    41 43 47 49
    53 59
    61 67
    71 73 77 79
    83 89
    91 97

    Infine, seleziono 7 ed elimino i multipli di 7.

    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

    I numeri restanti nella tabella sono i numeri primi da 2 a 100.

    E così via.

     


     
    Segnalami un errore, un refuso o un suggerimento per migliorare gli appunti

    FacebookTwitterLinkedinLinkedin
    knowledge base

    I numeri primi