Provjerite je li broj na Java-i prost

1. Uvod

Prvo, idemo preko neke osnovne teorije.

Jednostavno rečeno, broj je prost ako je djeljiv samo s jednim i sa samim brojem. Neprosti brojevi nazivaju se složeni brojevi. A broj jedan nije ni prosti ni složeni.

U ovom ćemo članku pogledati različite načine provjere primarnosti broja u Javi.

2. Prilagođena implementacija

Ovim pristupom možemo provjeriti može li broj između 2 i (kvadratni korijen broja) točno podijeliti broj.

Vratit će se sljedeća logika pravi ako je broj prost:

javna logička vrijednost isPrime (int broj) {return broj> 1 && IntStream.rangeClosed (2, (int) Math.sqrt (broj)) .noneMatch (n -> (broj% n == 0)); }

3. Korištenje BigInteger

BigInteger klasa obično se koristi za pohranu velikih brojeva, tj. onih većih od 64 bita. Pruža nekoliko korisnih API-ja za rad s int i dugo vrijednosti.

Jedan od tih API-ja je isProbablePrime. Ovaj se API vraća lažno ako je broj definitivno složen i vraća se pravi ako postoji neka vjerojatnost da će biti prost. Korisno je kada se radi s velikim cijelim brojevima jer može biti prilično intenzivno izračunavanje da bi se u potpunosti provjerile.

Kratka napomena - the isProbablePrime API koristi testove primarnosti "Miller - Rabin i Lucas - Lehmer" kako bi provjerio je li broj vjerojatno prost. U slučajevima kada je broj manji od 100 bitova, koristi se samo test "Miller - Rabin", inače se oba testa koriste za provjeru primatnosti broja.

Test "Miller-Rabin" ponavlja fiksni broj puta kako bi se odredio primarnost broja, a taj se broj ponavljanja određuje jednostavnom provjerom koja uključuje duljinu bita broja i vrijednost sigurnosti koja se prosljeđuje API-ju:

javni boolean isPrime (int broj) {BigInteger bigInt = BigInteger.valueOf (broj); vratiti bigInt.isProbablePrime (100); }

4. Korištenje matematike Apache Commons

Apache Commons Math API pruža metodu imenovanu org.apache.commons.math3.primes.Primes, koje ćemo upotrijebiti za provjeru primarnosti broja.

Prvo, moramo uvesti biblioteku Apache Commons Math dodavanjem sljedeće ovisnosti u našu pom.xml:

 org.apache.commons commons-math3 3.6.1 

Najnoviju verziju commons-math3 možete pronaći ovdje.

Provjeru bismo mogli izvršiti samo pozivanjem metode:

Primes.isPrime (broj);

5. Zaključak

U ovom brzom zapisu vidjeli smo tri načina provjere primarnosti broja.

Kôd za to možete pronaći u paketu com.baeldung.algorithms.primechecker preko na Githubu.