Связана ли точность nextProbablePrime () с размером входного значения?

Question

Я использую BigInteger nextProbablePrime в домашнем задании для вычисления следующего простого числа, которое я могу использовать для изменения размера хеш-таблицы, использующей квадратичное зондирование.

В таблице хранятся элементы данных, считанные из файла. Файл примера, который мне дали, содержит только 100 элементов, но я не могу предположить, что это максимальный набор данных, на котором будет проверяться моя программа.

Мне интересно, есть ли какая-либо связь между размером значения, которое я передаю в nextProbablePrime, и вероятностью того, что он правильно вернет простое число? Другими словами, есть ли число, ниже которого nextProbablePrime гарантированно будет точным? Разумно ли мне полагаться на это?

Answer 1

Поскольку «вероятность того, что число, возвращаемое этим методом, является составной, не превышает 2^-100», я думаю, что разумно полагать, что оно возвращает простое число.

Answer 2

Это хорошо для вашей цели.

Лучше было бы использовать предварительно вычисленный список размеров хеш-таблиц.Вам, вероятно, нужно только полдюжины или около того;выбирайте на основе ожидаемого размера вашей хеш-таблицы и увеличивайте, если коэффициент загрузки становится слишком большим.

Общий урок состоит в том, чтобы использовать все возможные методы, чтобы уменьшить сложность вашего кода.Вы пишете хеш-таблицу.Вам не нужно беспокоиться о простых числах.

Answer 3

nextProbablePrime () фактически используется для криптографических операций, которые требуют нахождения (действительно) огромных чисел, которые «вероятно просты». Метод nextProbablePrime () возвращает число, простое с вероятностью 2 ^ -100.

Я не думаю, что такой метод полезен для ваших нужд. Для разумных чисел (например, размера хеш-таблицы) вы можете просто проверить, простое ли число, используя простую самодельную реализацию, особенно если требуется высокая производительность.