Primo?

Un numero intero positivo, n, è primo se n > 1 e se i suoi unici divisori sono 1 e se stesso.
[N.B.: Il numero 1 non viene considerato perchè è (l'unico) numero invertibile per la moltiplicazione, cioè esiste un numero intero y tale che 1.y = 1. Infatti basta prendere y = 1.]
I numeri primi minori a 20 sono: 2, 3, 5, 7, 11, 13, 17, 19.
Negli "Elementi" di Euclide si trova la dimostrazione del fatto che esiste un'infinità di numeri primi.
Si ragiona per assurdo, usando il fatto che ogni numero possiede un divisore primo. Se p1=2, p2=3,...,pN sono tutti i numeri primi, si considera M =p1.p2...pN +1. Nessuno dei pi divide M, quindi M non ammette alcun divisore primo: assurdo.
Distribuzione dei numeri primi.
Sia p(x) la funzione definita da p(x)= il numero di numeri primi minori o uguali a x.
Un celebre teorema (dimostrato indipendentemente da Hadamard e de la Vallée-Poussin, 1896) asserisce che, per x molto grande, p(x) si comporta come x/log(x) [logaritmo in base e]. La congettura di Riemann, il problema aperto forse più importante di tutta la matematica, stabilisce una migliore approssimazione di p(x).

Il programma testa se un numero n <1.000.000.000 (un miliardo, per chi non fosse abituato a queste cifre) è primo.
Perchè ci limitiamo ad un miliardo? In realtà si potrebbe andare un pò più in là, ma comunque bisognerebbe fermarsi. I numeri sono spazi di memoria nel computer, e questi spazi sono in numero finito. Per esempio il formato int di java, arriva fino a 2 miliardi e rotti; il formato long va fino a 9.223.372.036.854.775.807. Ma comunque si ferma!
Il computer non conosce l'infinito!! (mentre noi sì).
Il programma è molto semplice: si parte da i = 2, si guarda se i divide n, se sì abbiamo finito: n non è primo e n = i. (n/i). Altrimenti si incrementa i di uno (i+=1) e si ricomincia. Si va avanti fino a raggiungere la radice quadrata di n, se non abbiamo trovato nessun divisore, allora n è primo.
N.B.: Se n = ab, allora il più piccolo tra a e b è minore della radice quadrata di n.