Controlla se un numero è primo in Java

1. Introduzione

Per prima cosa, esaminiamo una teoria di base.

In poche parole, un numero è primo se è divisibile solo per uno e per il numero stesso. I numeri non primi sono chiamati numeri composti. E il numero uno non è né primo né composto.

In questo articolo, daremo uno sguardo a diversi modi per verificare la primalità di un numero in Java.

2. Un'implementazione personalizzata

Con questo approccio, possiamo verificare se un numero compreso tra 2 e (radice quadrata del numero) può dividere accuratamente il numero.

La seguente logica restituirà true se il numero è primo:

public boolean isPrime(int number) { return number > 1 && IntStream.rangeClosed(2, (int) Math.sqrt(number)) .noneMatch(n -> (number % n == 0)); }

3. Utilizzo di BigInteger

La classe BigInteger viene generalmente utilizzata per memorizzare interi di grandi dimensioni, ovvero quelli maggiori di 64 bit. Fornisce alcune API utili per lavorare con valori int e long .

Una di queste API è isProbablePrime . Questa API restituisce false se il numero è sicuramente un composto e restituisce true se esiste una certa probabilità che sia primo. È utile quando si tratta di numeri interi di grandi dimensioni perché può essere un calcolo piuttosto intenso per verificarli completamente.

Un rapido laterale nota - le isProbablePrime usi API ciò che è noto come “Miller - Rabin e Lucas - Lehmer” test di primalità per verificare se il numero è probabilmente primo. Nei casi in cui il numero è inferiore a 100 bit, viene utilizzato solo il test “Miller - Rabin”, altrimenti entrambi i test vengono utilizzati per verificare la primalità di un numero.

Il test "Miller-Rabin" itera un numero fisso di volte per determinare la primalità del numero e questo conteggio delle iterazioni è determinato da un semplice controllo che coinvolge la lunghezza in bit del numero e il valore di certezza passato all'API:

public boolean isPrime(int number) { BigInteger bigInt = BigInteger.valueOf(number); return bigInt.isProbablePrime(100); }

4. Utilizzo di Apache Commons Math

Apache Commons Math API fornisce un metodo denominato org.apache.commons.math3.primes.Primes, che utilizzeremo per controllare la primalità di un numero.

Innanzitutto, dobbiamo importare la libreria Apache Commons Math aggiungendo la seguente dipendenza nel nostro pom.xml :

 org.apache.commons commons-math3 3.6.1 

L'ultima versione di commons-math3 può essere trovata qui.

Potremmo fare il controllo semplicemente chiamando il metodo:

Primes.isPrime(number);

5. conclusione

In questo breve articolo, abbiamo visto tre modi per verificare la primalità del numero.

Il codice per questo può essere trovato nel pacchetto com.baeldung.algorithms.primechecker su Github.