Generatore N numeri primi Java

[LeleFT]

Piccola miglioria al codice di Leonerd

boolean isPrime (int n) {
   if (n%2 == 0) return false;
   for(int i=3; i < Math.sqrt(n); i+=2)
      if(n%i==0) 
         return false;

   return true;
}

In questo modo evitiamo di controllare tutti i numeri pari compresi fra 3 e la radice del numero.

La dimostrazione del fatto che sia sufficiente iterare fino alla radice quadrata del numero è piuttosto intuitiva.
Se un numero N non è primo, esiste almeno una coppia di numeri (X e Y) tale per cui X * Y = N
Dato Z la radice quadrata di N, se trovo un divisore X di N maggiore di Z è ovvio che devo averne trovato prima uno (Y) minore di Z (poichè per ottenere N devo avere X * Y e Y non può certo essere maggiore di Z). Il caso "pessimo" è proprio quando X e Y sono uguali... ovvero N = X * X e X è appunto la radice quadrata di N.


Ciao.