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.