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 alla radice $ \sqrt{n} $ di n

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

    Un esempio pratico

    Voglio trovare i numeri primi fino a cento.

    Per prima cosa scrivo i numeri da 2 a 100 in una tabella.

      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

    Nota. Il numero 1 non va messo nella tabella perché il numero uno non è considerato un numero primo, in quanto la sua fattorizzazione non è unica. Ad esempio posso fattorizzare 1 con tutte le potenze di 1. $$ 1 = 1^1=1^2=1^3 ... $$ Un numero primo, per definizione, è divisibile per uno e per se stesso e la sua fattorizzazione è unica, indipendentemente dall'ordine dei fattori.

    Per trovare i primi da 1 a 100 mi basta eliminare dalla tabella i multipli degli interi da 2 alla radice di n=100, $ \sqrt{100}=10 $, ossia da 2 a 10.

    Seleziono 2 ed elimino tutti i multipli di 2 dalla tabella.

      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      

    Non essendoci più il 4 in tabella, è inutile esaminarlo perché so già che non è un numero primo.

    Quindi, il numero successivo è 5. Lo seleziono ed elimino i multipli di 5 dalla tabella.

      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 dalla tabella.

      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      

    Non ci sono altri numeri minori di 10 da esaminare nella tabella, quindi l'algoritmo si conclude qui.

    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

    FAQ