I numeri Primi

Definizione 

Un numero naturale n (n>1) si dice primo se ha due divisori: sé stesso e 1.

Per  esempio 

  • il numero 29 ha 2 divisori: 1, 29 quindi è primo
  • il numero 28 ha sei divisori: 1, 2, 4, 7, 14, 28 quindi non è primo

Nota che 1 non viene considerato numero primo. Ci sono diversi giustificazioni per questo fatto: la più intuitiva è che non sarebbe più valido uno dei principali teoremi sui numeri il quale afferma che la scomposizione di un numero in fattori primi è unica. 
esempio 12= 1*22*3, ma anche 12*22*3 ecc.
Un numero non primo viene detto numero composto.

Ecco i numeri primi minori di 200:

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, etc.

Il crivello di Eratostene

Eratostene (275-194 A.C., Greco) escogitò un procedimento detto 'crivello' per scoprire i numeri primi. Il crivello di Eratostene funziona come uno scolapasta che fa passare l'acqua e trattiene gli spaghetti: fa passare i numeri composti trattenendo quelli primi.

Ad esempio prendiamo i numeri da 1 a 100:


             1   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
  1. Eliminiamo l' 1 che non è primo.
  2. Evidenziamo il  2, che è  più piccolo numero primo. Quindi eliminiamo ciascun multiplo di 2; in altre parole tutti i numeri pari.
  3. Evidenziamo il  3, il numero primo successivo al 2. Quindi eliminiamo tutti i multipli di 3. Alcuni come il 6, saranno già stati eliminati come multipli di 2.
  4. Evidenziamo quindi il 5 ed eliminiamo tutti i successivi multipli.
Continuando in questo modo rimarranno evidenziati tutti i numeri primi minori di 100.
 
Due numeri si dicono invece primi tra di loro se non hanno fattori in comune. Ad esempio sono primi tra di loro 15 e 16, non lo sono 12 e 15.