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.


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