[Java] Trovare i numeri primi in modo lazy usando Stream

Spesso, per verificare se n è un numero primo, si divide n per tutti i numeri da 2 a n - 1 e si controlla se è divisibile.

In questo metodo, applichiamo alcune ottimizzazioni per migliorarlo in modo più efficiente e utilizziamo Stream per applicare la valutazione pigra.

Metodo Naive

Di seguito è riportato un metodo naive per verificare se n è un numero primo.

Miglioramenti

• Quando n = a x b, possiamo assumere che a > b senza perdere generalità.
  Cioè, è sufficiente controllare i fino a sqrt(n). L'operazione sqrt() è costosa, quindi può essere sostituita dalla condizione i * i <= n.
• I numeri primi maggiori di 5 hanno la forma 6k ± 1. Quindi, possiamo ridurre il numero di controlli incrementando i di 6.

Metodo Migliorato

Applicazione della Valutazione Pigra con Stream

Gli Stream di Java, a differenza delle List, non eseguono l'operazione immediatamente quando viene definita.

Rimangono in uno stato di attesa, con la definizione di come calcolare ogni elemento, e eseguono solo l'operazione necessaria per ottenere l'elemento richiesto.

Utilizzando questa caratteristica, possiamo creare uno Stream che trova i numeri primi nel seguente modo.

Risultato dell'Esecuzione

Codice completo

Risultato dell'esecuzione