Generatore N numeri primi Java

[Nuc]

Salve a tutti, sono Dario e sono nuovo sul forum. Avrei bisogno di un piccolo aiuto, ci ho ragionato un po' ma sono giunto a conclusioni errate o poco efficienti.

Non riesco a trovare l'algoritmo che mi crei in modo rapido il milionesimo numero primo.
(Nb: non i numeri primi tra 0 e 1 milione, ma proprio il milionesimo !)

Se riusciste a darmi una mano in qualsiasi modo ve ne sarei grato. Grazie a tutti attendo risposta

[Leonerd]

Io ho utilizzato questo metodo per determinare se un numero è primo:

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

Non so chi ha dimostrato che basta iterare fino alla radice di n invece che fino a n per determinare la primalità.

Ho provato a lanciare la ricerca del milionesimo e ha terminato in poco più di 20 secondi, trovando come numero 15.476.711

Non so se può essere considerato un risultato efficiente, prova a cercare metodi migliori per determinare la primalità!

[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.