DEFINIZIONE: Un numero intero N è primo se è divisibile solo per 1 e per N
Risorse collegate
Se vuoi stampare la copia cartacea di tale argomento, puoi scaricare qui il PDF 
DEFINIZIONE: Un numero intero N è primo se è divisibile solo per 1 e per N
Questa definizione, però, non ci aiuta molto. Ci conviene esprimerla In altri termini: Un numero N è primo se non esistono divisori diversi da 1 e da N.
Da bambini ci hanno insegnato alcuni, criteri: divisibilità per 3, divisibilità per 5, 7, 11, 13...ma, a parte le prime due sono abbastanza cervellotiche e soprattutto non risolvono il problema in modo generale. In effetti, ad oggi, l'unico modo conosciuto per decidere se un numero N è primo o meno è quello di utilizzare la forza bruta dei calcolatori: si prova a dividere per 2; se non è divisibile si prova a dividere per 3; se non è divisibile si prova a dividere per 5 e così via... non appena trovo un divisore posso fermare la mia indagine e concludere che il numero N non è primo.
E se il divisore non lo trovo perché il numero è primo, quando mi fermo?
- La prima risposta, quella impulsiva, ci spinge a dire che bisogna fermarsi quando si arriva a N-1 (se N=10000, dovrei arrivare fino a 9999)
- Se ci ragioniamo un po', invece, ci accorgiamo che basta arrivare alla metà di N (se N=10000, dovrei arrivare fino a 5000)
- Se poi siamo appena un po' più esperti, dovremmo sapere che basta arrivare alla √N
(se N=10000, dovrei fare 100... ma in effetti, scartando i numeri pari, ne faccio solo 50! un bel risparmio di cicli rispetto al metodo 1 e 2) Domanda: perchè scarto i numeri pari? Perchè se fosse divisibile per un numero pari, mi sarei già fermato al primo tentativo, quando ho provato a dividere per 2.
Riportiamo qui di seguito la codifica in linguaggio C dell'algoritmo esaminato:
/******************************************************************************Dato in input un numero N, dire se esso è un numero primo*******************************************************************************/#include <stdio.h>#include <iostream>#include <math.h>using namespace std;int main(){int n, divisore, ultimo_divisore, resto;printf("numero primo\n");cout<<"inserire un numero: ";cin>>n;divisore=2;resto=n%divisore;if(resto!=0){ultimo_divisore=sqrt(n);divisore=3;do{resto=n%divisore;divisore=divisore+2;}while(resto!=0 && divisore<=ultimo_divisore);}if (resto!=0){cout<< n<< " e' primo";}else{cout<< n<< " non e' primo";}return 0;}
COMMENTO:
- n: numero in input
- divisore: candidato divisore. Assumerà i valori 2,3,5,7,9...
- ultimo_divisore: conterrà il valore di √N
- resto: contiene il resto della divisione fra n e divisore.
linee 12-14 acquisizione del numero n
linee 16-17 si prova a dividere per 2
linea 18 se il resto precedente è zero la codizione è falsa e si salta direttamente alla linea 27
linea 19 si calcola l'ultimo divisore da provare
linea 20 si imposta come prossimo divisore 3
linee 21-24 ciclo in cui si calcola il resto della divisione fra n e divisore e si predispone il divisore per il prossimo ciclo (divisore=divisore+2;) il ciclo termina o quando il resto è zero oppure quando divisore ha superato ultimo_divisore
linee 27-31 viene emesso il risultato, a seconda del valore contenuto in resto