Próbuję wygenerować losową liczbę pierwszą typu BigInteger, która jest między wartością minimalną i maksymalną, które dostarczam.Java BigInteger liczby pierwsze
Jestem świadomy BigInteger.probablePrime (int bitlength, random), ale nie jestem pewien, jak lub nawet jeśli bitlength tłumaczy się na wartość max/min wyjściowego prime.
Dzięki, Steven1350
BigInteger.probablePrime(bitLength, random) ma zamiar powrócić (prawdopodobny) sile określonej długości bitowej. Przekłada się to na maksymalną wartość 2^bitlength - 1 i minimum 2^(bitlength - 1). Tak jak nienawidzę go jako odpowiedzi, to prawdopodobnie najlepiej, chyba że chcesz zacząć zagłębiać się w teorię liczb.
To, co musisz zrobić, to dowiedzieć się długości bitów, których wymaga twój zasięg, a następnie przekazać je do probablePrime(), aż odzyskasz moc, która znajduje się we właściwym zakresie. Odpowiedź
jprete jest w porządku, jeśli stosunek max/min nie jest blisko 1.
Jeśli masz wąski zakres, najlepiej jest prawdopodobnie tylko zrobić coś jak następuje:
// this is pseudocode:
//
// round min down to multiple of 6, max up to multiple of 6
min6 = floor(min/6);
max6 = ceil(max/6);
maybePrimeModuli = [1,5];
do
{
b = generateRandom(maybePrimeModuli.length);
// generate a random offset modulo 6 which could be prime
x = 6*(min6 + generateRandom(max6-min6)) + b;
// generate a random number which is congruent to b modulo 6
// from 6*min6 to 6*max6-1
// (of the form 6k+1 or 6k+5)
// the other choices 6k, 6k+2, 6k+3, 6k+4 are composite
} while not isProbablePrime(x);
The density of primes jest dość wysoki ogólnie, to w zasadzie 1 w log (x), więc nie powinieneś powtarzać zbyt wiele razy, aby znaleźć liczbę pierwszą. (tylko dla przykładu: dla liczb około 10 , jedna na 52 całkowite liczby jest liczbą pierwszą, powyższy kod zawraca tylko 2 z każdych 6 liczb, więc skończysz w pętli średnio 17 razy dla liczb około 10 .)
Tylko upewnij się, że masz dobry test pierwotności, a Java BigInteger ma jeden.
Jako ćwiczenie dla czytelnika, rozszerz powyższą funkcję, aby odfiltrować więcej liczb zespolonych z wyprzedzeniem za pomocą 30k + x (modulo 30, są 22 moduły, które są zawsze złożone, tylko 8 pozostałych, które mogą być pierwszymi) lub 210 k + x.
edytuj: patrz również US patent #7149763 (OMFG !!!)
Interesujące. Od Doc, "prawdopodobieństwo, że zwrócone BI jest kompozytowe wynosi <2^-100", naprawdę mało prawdopodobne! Czy wiesz przypadkiem złożoność tej metody? –
Zamiast wywoływania probalePrime z bitlength, zakres wywołania można utworzyć losową dużą liczbę całkowitą w zakresie i wywołać nextProbablePrime na nim. Spowoduje to wygenerowanie liczby pierwszej szybciej, niż wielokrotne wywołanie problePrime. Z cours będziesz musiał zmierzyć się z sytuacją, gdzie reult jest większy niż maksymalna wartość twojego zasięgu. –