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.
