Controleer of een nummer primair is in Java

1. Inleiding

Laten we eerst wat basistheorie bespreken.

Simpel gezegd, een getal is een priemgetal als het alleen deelbaar is door één en door het getal zelf. De niet-priemgetallen worden samengestelde getallen genoemd. En nummer één is geen priemgetal of samengesteld.

In dit artikel zullen we verschillende manieren bekijken om de primaliteit van een getal in Java te controleren.

2. Een implementatie op maat

Met deze aanpak kunnen we controleren of een getal tussen 2 en (vierkantswortel van het getal) het getal nauwkeurig kan delen.

De volgende logica komt terug waar als het nummer een priemgetal is:

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

3. Met behulp van BigInteger

BigInteger class wordt over het algemeen gebruikt voor het opslaan van grote gehele getallen, d.w.z. die groter zijn dan 64 bits. Het biedt een aantal handige API's om mee te werken int en lang waarden.

Een van die API's is de isProbablePrime. Deze API keert terug false als het nummer beslist een samengesteld getal is en terugkeert waar als er enige kans is dat het een priemgetal is. Het is handig bij het omgaan met grote gehele getallen, omdat het een behoorlijk intensieve berekening kan zijn om deze volledig te verifiëren.

Een snelle kanttekening - de isProbablePrime API gebruikt wat bekend staat als "Miller - Rabin en Lucas - Lehmer" primaliteitstests om te controleren of het getal waarschijnlijk een priemgetal is. In gevallen waarin het aantal kleiner is dan 100 bits, wordt alleen de "Miller - Rabin" -test gebruikt, anders worden beide tests gebruikt om de primaliteit van een getal te controleren.

De "Miller-Rabin" -test herhaalt een vast aantal keren om de primaliteit van het getal te bepalen en deze iteratietelling wordt bepaald door een eenvoudige controle waarbij de bitlengte van het getal en de zekerheidswaarde die aan de API worden doorgegeven, zijn betrokken:

openbare boolean isPrime (int nummer) {BigInteger bigInt = BigInteger.valueOf (nummer); retourneer bigInt.isProbablePrime (100); }

4. Apache Commons Math gebruiken

Apache Commons Math API biedt een methode met de naam org.apache.commons.math3.primes.Primes, die we zullen gebruiken om de primaliteit van een getal te controleren.

Eerst moeten we de Apache Commons Math-bibliotheek importeren door de volgende afhankelijkheid toe te voegen aan onze pom.xml:

 org.apache.commons commons-math3 3.6.1 

De laatste versie van de commons-math3 is hier te vinden.

We zouden de controle kunnen uitvoeren door de methode aan te roepen:

Primes.isPrime (nummer);

5. Conclusie

In dit korte artikel hebben we drie manieren gezien om te controleren of het nummer primair is.

De code hiervoor vindt u in het pakket com.baeldung.algorithms.primechecker over op Github.