niedziela, czerwca 22, 2008

BigInteger i liczby pierwsze ;-)

Pytanie:Jak szybko sprawdzić w Java'ie czy dowolnie duża liczba jest pierwsza? :-)Odpowiedź:Użyć metody isProbablePrime(int) klasy BigInteger :-)Dzięki temu, że metoda ta używa testu prawdopodobieństwa Miller'a-Rabina, możemy by z prawdopodobieństwem 1-1/1024 ustalić czy dana liczba jest liczbą pierwszą, użyć kodu:
BigInteger bi = new BigInteger(str);if (bi.isProbablePrime(10)) { System.out.println(bi+" is [probably ;-)] prime :-)");}
By zrobić to z prawdopodobieństwem 1-1/1048576 wystarczy jako parametr do metody isProbablePrime(int) przekazać 20 :-) W ogólności prawdopodobieństwo to jest równe 1-2-n ;-)Przy okazji BigInteger może nam także znaleźć liczbę prawdopodobnie pierwszą ;-)Czyż Java nie jest fajna? :-)


Podobne postybeta
Wydało się ;-)
Spadochronowy atak na Wawel - czyli wolne GWT
Droga do celu..
Java i liczby pierwsze, odsłona druga
Chmurka prawdopodobieństwa