Nell'ambito della verifica della primalità in Java, viene proposto un metodo per migliorare l'efficienza del metodo tradizionale che verifica la divisibilità da 2 a n-1, riducendo la verifica fino a sqrt(n) e utilizzando il formato 6k±1.
Utilizzando Stream, è possibile applicare la valutazione lazy, generando uno Stream che trova i numeri primi eseguendo le operazioni solo quando necessario.
Attraverso le migliorie e l'utilizzo di Stream presentati in questo articolo, è possibile implementare un algoritmo per la verifica della primalità in modo più efficiente.
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.