Найдите следующее простое число в Python
У меня есть функция, которая принимает число (например, 5) и возвращает первое простое число после введенного числа (в данном случае это будет 7).
Однако этот код не работает (всегда возвращает 2). Где ошибка?
8 ответов
У вас есть несколько ошибок, в первую очередь np явно предназначен для использования в качестве потенциальных простых чисел (он начинается с n+1 которое является первым потенциальным числом, которое соответствует вашему критерию «первое простое число после входного числа»), и все же вы добавляете x в ваш основной список, который из range(2,199) , вы должны использовать:
Ваш тест на простоту также неверен, поэтому вы должны использовать:
Наконец, вы не можете добавить число, если это условие истинно в одном случае, оно должно быть истинным во всех случаях (где x — целое число, которое удовлетворяет 2 <= x < j ), поэтому вам следует переключить второй набор циклов for ( x цикл должен быть внутренним циклом), и вы также должны выполнять цикл только до j-1 (число проверяемых). Кроме того, вы должны вместо этого отказаться от добавления элемента, если j % x == 0 :
В результате получается следующий код:
И тестовый запуск:
Обратите внимание, что есть несколько других улучшений эффективности, которые можно сделать, но этот ответ фокусируется на ошибках, а не на улучшениях.
Есть ли библиотека Python для перечисления простых чисел?
Есть ли в Python библиотечная функция, которая может перечислять простые числа (последовательно)?
Я нашел этот вопрос Самый быстрый способ перечислить все простые числа ниже N, но я предпочитаю использовать чью-то надежную библиотеку, чем создавать собственную. Я был бы рад сделать import math; for n in math.primes:
Ответы (4)
Другой вариант — SymPy. Это библиотека Python для символической математики. Он предоставляет несколько функций для прайма.
Вот несколько примеров.
Библиотека gmpy2 имеет функцию next_prime (). Эта простая функция создаст генератор, который обеспечит бесконечный запас простых чисел:
Если вы будете многократно перебирать простые числа, создание и повторное использование таблицы всех простых чисел ниже разумного предела (скажем, 1000000) будет быстрее. Вот еще один пример использования gmpy2 и решета Эратосфена для создания таблицы простых чисел. primes2 () сначала возвращает простые числа из таблицы, а затем использует next_prime ().
Вы можете настроить table_limit в соответствии со своими потребностями. Большие значения потребуют больше памяти и увеличат время запуска для первого вызова primes (), но это будет быстрее для повторных вызовов.
Примечание: я сопровождаю gmpy2.
Задав этот вопрос, я написал оболочку Python вокруг primesieve библиотеки C ++, которая впоследствии была принята сопровождающим primesieve. https://github.com/kimwalisch/primesieve-python
Не существует алгоритма постоянного времени для генерации следующего простого числа; вот почему для большинства библиотек требуется верхняя граница. На самом деле это огромная проблема, которую необходимо было решить для цифровой криптографии. RSA выбирает достаточно большие простые числа, выбирая случайное число и проверяя простоту, пока не найдет простое число.
Учитывая произвольное целое число N , единственный способ найти следующее простое число после N — это пройти через N+1 до неизвестного простого P , проверяя простоту.
Тестирование на простоту очень дешево, и для этого существуют библиотеки Python: алгоритм AKS Primes в Python
Для функции test_prime итератор с бесконечным числом простых чисел будет выглядеть примерно так:
Есть много эвристик, которые можно использовать для ускорения процесса. Например, пропускайте четные числа или числа, делящиеся на 2, 3, 5, 7, 11, 13 и т. Д.
Как написать итератор простых чисел
Задача состоит в следующем. На входе есть например число 11. При каждом вызове next выводится меньшее простое число 7 следующий next выводит 5 и так далее. Как только достигли 2 выводим ошибку Stopiteration. Обязательное условие задачи использовать написанный в ручную итератор и вызов должен выглядеть так как в примере. В моем понимаеии нужно создать список простых чисел по убыванию и при каждом вызове через next выводить по одному числу. Вот так :
Получилось создать список с простыми числами но не получается вывести их по очередно через next. Помогите пожалуйста разобраться что не так
У задачи есть две стороны: математическая и технологическая. Математическую я предельно упростил — простота числа проверяется по определению. Можно сделать быстрее, но пока так.
Технологическая сторона. Я сделаю LowerPrime аналогом range. В Питоне range — неизменяемая последовательность. Из последовательности можно получить сколько угодно итераторов. Все итераторы полностью независимы. Демонстрация:
Схема "одна последовательность — много итераторов" нужна чтобы работал код вроде:
Без разных итераторов второй цикл не выполнится, так как первый исчерпал свой итератор полностью и нам нужен новый итератор.
Тоже самое для списка. Список один, итераторов много:
Становится ясно, что нужны два класса. Для списка убывающих простых LowerPrime , для итераторов LowerPrimeIter . Список простых заранее можно не составлять. Каждый вызов next продолжает поиск простых с того места, где итератор остановился раньше:
Основной генератор простых чисел в Python
Просто нужна была обратная связь с генератором простых чисел. например это нормально, он использует много ресурсов и т.д. Он не использует библиотеки, он довольно прост, и это отражает мое текущее состояние навыков программирования, поэтому не сдерживайтесь, как я хочу узнать.
5 ответов
Существует несколько оптимизаций:
Пример:
- Обложка базовых футляров
- Только итерация до квадратного корня n
Приведенный выше пример не генерирует простые числа, но проверяет их. Вы можете адаптировать те же самые оптимизации к вашему коду:)
Один из наиболее эффективных алгоритмов, найденных на Python, можно найти в следующем ответе на вопрос (используя сито):
Моя собственная адаптация ситового алгоритма:
На моем оборудовании я могу быстро сгенерировать первые миллионы простых чисел (учитывая, что это написано на Python):
Вот стандартный способ генерации простых чисел, адаптированных из версии С#, по адресу: Самый элегантный способ создания первичного номера
Будучи Python, обычно лучше возвращать генератор, который возвращает бесконечную последовательность простых чисел, а не список.
ActiveState имеет список старших сит Eratosthenes recipes
Вот один из них, обновленный до Python 2.7, с помощью itertools count с аргументом шага, которого не было, когда был написан оригинальный рецепт:
Поскольку он является генератором, он намного эффективнее памяти, чем генерирует весь список. Так как он находит композит, он также эффективен с точки зрения вычислений.
Затем каждый последующий вызов возвращает следующее простое:
Затем вы можете получить список между границами (т.е. X-го числа от первого до простого числа X + Y. ) с помощью islice: