Какой самый эффективный алгоритм для нахождения ближайшего простого числа меньше заданного числа n?

Question

Задача
Дано число n, 2 <= n <= 2 ^ 63. N может быть простым. Найдите простое число p, наиболее близкое к n. </p>

Используя тот факт, что для всех простых чисел p, p> 2, p нечетно и p имеет форму 6k + 1 или 6k + 5, можно написать цикл из n − 1 в 2, чтобы проверить, является ли это число премьер. Поэтому вместо проверки всех чисел мне нужно проверять каждую нечетную из двух форм выше. Однако мне интересно, есть ли более быстрый алгоритм для решения этой проблемы? то есть некоторые ограничения, которые могут ограничивать диапазон чисел, должны быть проверены? Любая идея будет принята с благодарностью.

Answer 1

В действительности шансы найти простое число «высокие», поэтому проверка методом грубой силы при пропуске «тривиальных» чисел (чисел, делимых на маленькие простые числа) будет вашим лучшим подходом, учитывая то, что мы знаем о теории чисел на сегодняшний день.

[обновление] Слабая оптимизация, которую вы могли бы выполнить, похожа на сито Эратосфена, где вы определяете небольшую плавную границу и помечаете все числа в диапазоне около N как составные и тестируете толькочисла относительно простых к вашей гладкой основе.Вам нужно будет сделать свой диапазон и плавность достаточно малыми, чтобы не затмевать время выполнения сравнительного «затратного» основного теста.

Answer 2

Самая большая оптимизация, которую вы можете сделать, - это использовать быструю проверку простоты перед выполнением полного теста.Например, см. http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test для часто используемого теста, который быстро удалит большинство чисел как «вероятно, не простые».Только после того, как у вас есть веские основания полагать, что число является простым, вы должны попытаться должным образом доказать первичность.(Во многих случаях люди с радостью просто принимают, что, если он пройдет определенное количество испытаний теста Рабина-Миллера, он настолько прост, что вы можете просто принять этот факт.)