Ellenőrizze, hogy a szám elsődleges-e a Java-ban

1. Bemutatkozás

Először nézzünk át néhány alapvető elméletet.

Egyszerűen fogalmazva: egy szám akkor elsődleges, ha csak eggyel és magával a számmal osztható. A nem prímszámokat összetett számoknak nevezzük. Az első számú pedig nem elsődleges és nem összetett.

Ebben a cikkben megnézzük, hogyan lehet ellenőrizni egy Java számának elsődlegességét.

2. Egyedi megvalósítás

Ezzel a megközelítéssel ellenőrizhetjük, hogy egy 2 és (a szám négyzetgyöke) közötti szám pontosan el tudja-e osztani a számot.

A következő logika visszatér igaz ha a szám prím:

nyilvános logikai isPrime (int szám) {visszatérési szám> 1 && IntStream.rangeClosed (2, (int) Math.sqrt (szám)) .noneMatch (n -> (szám% n == 0)); }

3. Használata BigInteger

BigInteger osztály általában nagyméretű egész számok, azaz a 64 bitnél nagyobb számok tárolására szolgál. Néhány hasznos API-t biztosít a munkához int és hosszú értékek.

Az egyik ilyen API az isProbablePrime. Ez az API visszatér hamis ha a szám határozottan összetett és visszatér igaz ha van valamilyen valószínűség, hogy elsődleges. Hasznos, ha nagy egész számokkal foglalkozunk, mert meglehetősen intenzív számítás lehet ezek teljes ellenőrzése.

Gyors mellékjegyzet - a isProbablePrime Az API az úgynevezett „Miller - Rabin és Lucas - Lehmer” prímteszteket használja annak ellenőrzésére, hogy a szám valószínűleg elsődleges-e. Azokban az esetekben, amikor a szám kevesebb, mint 100 bit, csak a „Miller - Rabin” tesztet alkalmazzák, ellenkező esetben mindkét tesztet a szám prímájának ellenőrzésére használják.

A „Miller-Rabin” teszt rögzített számú ismétlést végez a szám elsődlegességének meghatározásához, és ezt az iterációs számot egy egyszerű ellenőrzés határozza meg, amely magában foglalja a szám bithosszát és az API-nak átadott bizonyosságértéket:

nyilvános logikai isPrime (int szám) {BigInteger bigInt = BigInteger.valueOf (szám); return bigInt.isProbablePrime (100); }

4. Az Apache Commons Math használata

Az Apache Commons Math API nevű metódust biztosít org.apache.commons.math3.primes.Primes, amelyet egy szám elsődlegességének ellenőrzésére fogunk használni.

Először importálnunk kell az Apache Commons Math könyvtárat a következő függőség hozzáadásával pom.xml:

 org.apache.commons commons-math3 3.6.1 

A commons-math3 legújabb verziója itt található.

Az ellenőrzést csak a módszer meghívásával tehetjük meg:

Primes.isPrime (szám);

5. Következtetés

Ebben a gyors írásban három módszert láthattunk a szám elsődlegességének ellenőrzésére.

Ennek kódja megtalálható a csomagban com.baeldung.algorithms.prechecher át a Githubon.


$config[zx-auto] not found$config[zx-overlay] not found