streamalism.org

1. Introduktion

Lad os først gå over nogle grundlæggende teorier.

Kort sagt, et tal er primært, hvis det kun kan deles med et og med selve tallet. De ikke-primtal kaldes sammensatte tal. Og nummer et er hverken prime eller sammensat.

I denne artikel vil vi se på forskellige måder at kontrollere et tal i Java på.

2. En brugerdefineret implementering

Med denne tilgang kan vi kontrollere, om et tal mellem 2 og (kvadratroden af ​​nummeret) nøjagtigt kan dele tallet.

Følgende logik vender tilbage rigtigt hvis tallet er prime:

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

3. Brug BigInteger

BigInteger klasse bruges generelt til lagring af store heltal, dvs. dem der er større end 64 bit. Det giver et par nyttige API'er til at arbejde med int og lang værdier.

En af disse API'er er isProbablePrime. Denne API vender tilbage falsk hvis tallet bestemt er et sammensat og returnerer rigtigt hvis der er en vis sandsynlighed for, at det er primært. Det er nyttigt, når du beskæftiger dig med store heltal, fordi det kan være en ret intensiv beregning at kontrollere disse fuldt ud.

En hurtig side-note - det isProbablePrime API bruger det, der er kendt som ”Miller - Rabin og Lucas - Lehmer” -primalitetstest for at kontrollere, om antallet sandsynligvis er prime. I tilfælde, hvor antallet er mindre end 100 bits, anvendes kun "Miller - Rabin" -testen, ellers bruges begge test til at kontrollere et tales primalitet.

"Miller-Rabin" test gentager et fast antal gange for at bestemme det primære antal, og dette iterationstælling bestemmes af en simpel kontrol, der involverer bitlængden af ​​nummeret og den sikkerhedsværdi, der sendes til API:

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

4. Brug af Apache Commons Math

Apache Commons Math API giver en metode med navnet org.apache.commons.math3.primes.Primes, som vi vil bruge til at kontrollere et tales primalitet.

Først skal vi importere Apache Commons Math-biblioteket ved at tilføje følgende afhængighed i vores pom.xml:

 org.apache.commons commons-math3 3.6.1 

Den seneste version af commons-math3 kan findes her.

Vi kunne udføre kontrollen bare ved at kalde metoden:

Primes.isPrime (nummer);

5. Konklusion

I denne hurtige opskrivning har vi set tre måder at kontrollere, om nummeret er primalt.

Koden til dette findes i pakken com.baeldung.algorithms.primechecker over på Github.