Я пытаюсь создать случайное простое число типа BigInteger, то есть между минимальным и максимальным значением, которое я поставлю.Простые числа Java BigInteger
Я знаю, что BigInteger.probablePrime (int bitlength, random), но я не уверен, как или даже если длина бита переводится в максимальное/максимальное значение выводимого праймера.
Спасибо, Steven1350
BigInteger.probablePrime(bitLength, random) собирается возвращать (вероятный) прайм указанной разрядности. Это переводит в максимальное значение 2^бит-длина - 1 и минимум 2^(длина бит-1). Насколько я ненавижу это как ответ, это, вероятно, ваш лучший выбор, если вы не хотите начать размышлять над теорией чисел.
Что вам нужно сделать, это выяснить длину бит, которую требует ваш диапазон, а затем передать их probablePrime(), пока вы не вернетесь к премьеру, находящемуся в правильном диапазоне. Ответ
jprete является штраф, если ваше отношение макс/мин не близко к 1.
Если у вас есть узкий диапазон, лучше всего, вероятно, просто сделать что-то вроде следующего:
// 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);
density of primes довольно высокий в целом, это в основном 1 в журнале (x), поэтому вам не придется повторять слишком много раз, чтобы найти простое число. (как пример: для чисел около 10 , каждое из 52 целых чисел в среднем представляет собой простое число. Вышеприведенный код беспокоит только 2 из каждых 6 чисел, так что вы закончите цикл в среднем по 17 раз для чисел около 10 .)
Просто убедитесь, что у вас хороший тест на первичность, а у Java BigInteger есть один.
В качестве упражнения для читателя расширьте описанную выше функцию, чтобы заблаговременно отфильтровывать более сложные числа с помощью 30k + x (по модулю 30, имеется 22 модуля, которые всегда являются составными, всего 8 оставшихся, которые могут быть первыми), или 210k + x.
редактировать: смотри также US patent #7149763 (OMFG !!!)
Интересно. Из Doc «вероятность того, что возвращаемый BI является составной, составляет <2^-100», довольно маловероятно! Знаете ли вы, случайно, сложность этого метода? –
Вместо вызова probalePrime с битовой длиной, вызываемой диапазоном вызовов, можно создать случайное большое целое число в диапазоне и вызывать на нем nextProbablePrime. Это приведет к тому, что простое число будет быстрее, если вы вызовете problePrime несколько раз. Конечно, вам придется заняться ситуацией, когда результат больше максимального значения вашего диапазона. –