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ą ;-)
Posted by przemelek at 00:35
Labels: ,

4 komentarze:

  1. a22.06.2008, 11:17

    czy ta metoda jest chociaż deterministyczna? :D

    -------------
    Racjonalny feveloper

    OdpowiedzUsuń
  2. przemelek22.06.2008, 11:22

    Nie :-) jest oparta o algorytm probabilistyczny, dlatego trzeba podać jej stopień pewności jaki chcemy osiągnąć.
    Ale działa tak, że liczba pierwsza test przejdzie na pewno, a liczba, która nie jest pierwsza przejdzie test pozytywnie tylko w 1 na 2^n przypadków.

    OdpowiedzUsuń
  3. Anonimowy24.03.2009, 11:46

    Witam, wiem że to stary post, ale trafiłem na niego szukając informacji o BigInteger w javie, z tego co wyczytałem w dokumentacji to metoda którą opisujesz nie nazywa się isProbablyPrime tylko isProbablePrime: http://java.sun.com/javase/6/docs/api/java/math/BigInteger.html#isProbablePrime(int)

    OdpowiedzUsuń
  4. przemelek24.03.2009, 11:52

    @wlk: masz czałkowitą racje, nie wiem jak mi to mogło przejść, bo wydaje mi sie, że wklejałem kod z Eclipse'a :-) Widać, jednak musiałem go ręcznie "przepisać":-)
    Dzięki za uwagę, już poprawiam.

    OdpowiedzUsuń

Subskrybuj: Komentarze do posta (Atom)