Skontrolujte, či je číslo v jazyku Java Prime
1. Úvod
Najskôr si povedzme niekoľko základných teórií.
Jednoducho povedané, číslo je prvočíslo, ak je deliteľné iba jedným a číslom samotným. Non-prvočísla sa nazývajú zložené čísla. A číslo jedna nie je ani primárne, ani zložené.
V tomto článku sa pozrieme na rôzne spôsoby, ako skontrolovať prvosť čísla v prostredí Java.
2. Vlastná implementácia
Pomocou tohto prístupu môžeme skontrolovať, či číslo medzi 2 a (druhá odmocnina čísla) dokáže číslo presne rozdeliť.
Nasledujúca logika sa vráti pravda ak je číslo prvočíslo:
public boolean isPrime (int number) {return number> 1 && IntStream.rangeClosed (2, (int) Math.sqrt (number)) .noneMatch (n -> (number% n == 0)); }
3. Používanie BigInteger
BigInteger trieda sa zvyčajne používa na ukladanie veľkých čísel, tj tých, ktoré sú väčšie ako 64 bitov. Poskytuje niekoľko užitočných rozhraní API pre prácu s int a dlho hodnoty.
Jedným z týchto rozhraní API je isProbablePrime. Toto API sa vracia nepravdivé ak je číslo určite zložené a vráti sa pravda ak existuje nejaká pravdepodobnosť, že to bude prvočíslo. Je to užitočné pri práci s veľkými celými číslami, pretože ich úplné overenie môže byť pomerne náročné.
Krátka poznámka - the isProbablePrime API používa testy originality známe ako „Miller - Rabin a Lucas - Lehmer“ na kontrolu, či je počet pravdepodobne prvočísel. V prípadoch, keď je počet menší ako 100 bitov, použije sa iba test „Miller - Rabin“, inak sa na kontrolu prvosti čísla použijú oba testy.
Test „Miller-Rabin“ iteruje pevný počet opakovaní, aby sa určila primalita čísla, a tento počet iterácií sa určuje jednoduchou kontrolou, ktorá zahŕňa bitovú dĺžku čísla a hodnotu istoty odovzdanú API:
public boolean isPrime (int number) {BigInteger bigInt = BigInteger.valueOf (number); návrat bigInt.isProbablePrime (100); }
4. Používanie Apache Commons Math
Apache Commons Math API poskytuje metódu s názvom org.apache.commons.math3.primes.Primes, ktoré použijeme na kontrolu prvosti čísla.
Najskôr musíme importovať knižnicu Apache Commons Math pridaním nasledujúcej závislosti do našej pom.xml:
org.apache.commons commons-math3 3.6.1
Najnovšiu verziu commons-math3 nájdete tu.
Kontrolu by sme mohli vykonať iba zavolaním metódy:
Primes.isPrime (číslo);
5. Záver
V tomto rýchlom zápise sme videli tri spôsoby kontroly prvosti čísla.
Kód je uvedený v balení com.baeldung.algoritmy.primechecker cez Github.