streamalism.org

1. Introduksjon

La oss først gå gjennom noen grunnleggende teorier.

Enkelt sagt, et tall er primært hvis det bare kan deles av ett og av selve tallet. De ikke-primtallene kalles sammensatte tall. Og nummer én er verken primær eller sammensatt.

I denne artikkelen vil vi se på forskjellige måter å kontrollere primiteten til et tall i Java.

2. En tilpasset implementering

Med denne tilnærmingen kan vi sjekke om et tall mellom 2 og (kvadratrot av tallet) kan dele tallet nøyaktig.

Følgende logikk kommer tilbake ekte hvis tallet er primtall:

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

3. Bruke BigInteger

BigInteger klasse brukes vanligvis til lagring av store størrelser, dvs. de som er større enn 64 bit. Det gir noen nyttige API-er for å jobbe med int og lang verdier.

En av disse APIene er isProbablePrime. Denne API-en returnerer falsk hvis tallet definitivt er et kompositt og returnerer ekte hvis det er noen sannsynlighet for at det blir prime. Det er nyttig når du arbeider med store heltall, fordi det kan være ganske intensiv beregning å verifisere disse fullt ut.

En rask side-note - den isProbablePrime API bruker det som er kjent som "Miller - Rabin og Lucas - Lehmer" -primalitetstester for å sjekke om tallet sannsynligvis er prime. I tilfeller der tallet er mindre enn 100 biter, brukes bare “Miller - Rabin” -testen, ellers brukes begge testene for å sjekke et talls primalitet.

“Miller-Rabin” -testen gjentar et fast antall ganger for å bestemme tallets primality, og denne iterasjonstallet bestemmes av en enkel sjekk som involverer bitlengden på tallet og sikkerhetsverdien som blir overført til API: et:

offentlig boolsk isPrime (int-nummer) {BigInteger bigInt = BigInteger.valueOf (number); returner bigInt.isProbablePrime (100); }

4. Bruke Apache Commons Math

Apache Commons Math API gir en metode som heter org.apache.commons.math3.primes.Primes, som vi vil bruke til å sjekke et talls primalitet.

Først må vi importere Apache Commons Math-biblioteket ved å legge til følgende avhengighet i vårt pom.xml:

 org.apache.commons commons-math3 3.6.1 

Den siste versjonen av commons-math3 finner du her.

Vi kan gjøre sjekken bare ved å ringe metoden:

Primes.isPrime (nummer);

5. Konklusjon

I denne raske oppskriften har vi sett tre måter å sjekke for primaliteten til tallet.

Koden for dette finner du i pakken com.baeldung.algorithms.primechecker over på Github.