Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Алгоритмы реализации поиска простых чисел на Python
Что такое простое число вы все, наверное знаете. Это натуральное число, у которого только два делителя 1 и само это число. Алгоритм определения, является ли это число целым не сложен. Нужно поискать его делители. Если их нет (кроме указанных выше), то число простое.
Общая постановка задачи будет такой: нужно найти все простые числа от 2 до заданного числа n.
Рассмотрим в начале программу, представленную на рисунке 1. Она ищет простые числа от a до b.
Пояснения к программе
Центральной в программе является функция prime(). Она возвращает True, если число простое и False, если число составное (не простое). Проверка делимости идёт до корня квадратного из из самого числа (math.sqrt(n)). Это и понятно, множители большие этого значения, имеют пару меньшую этого значения. Так зачем же проверять делимость на второй возможный парный множитель.
Не много изменим программу на рисунке 1. По сути не меняем алгоритм, а вынесем вывод вывод простых чисел в конец программы. Для этого будем запоминать простые числа в списке (см. Рисунок 2).
Пояснение к программе
Алгоритм, как я уже сказал не изменился. Честно говоря оптимизация оказалась не слишком эффективной. Улучшение не значительное. Однако есть.
Можно ли улучшить последний алгоритм? Можно, если учесть, что лишне учитывать чётные числа, так как они заведомо не простые. Другими словами можно просматривать числа с шагом 2 (см. Рисунок 3).
Пояснение к программе из рисунка 3
Поиск начинается с 3 и далее с шагом 2. Таким образом мы избегаем чётных чисел и уменьшаем количество шагов. Прирост производительности уже более существенен.
Решето Эратосфена
Ну и наконец программа (рисунок 4), реализующая алгоритм Решето Эратосфена, реализующий так называемое Решето Эратосфена. В чём суть алгоритма.
Начинаем с числа i=2, а затем "вычеркиваем все числа" вида m*i, при этом, конечно m*i <=b. Потом переходим к i=3 и т.д., пропуская, конечно, вычеркнутые.
Пояснение к программе
В программе самое интересное, как реализовать вычёркивание. Я реализовал очень просто. Все вычеркнутые числа помещаю в множество и каждый раз проверяю, попадает ли выбранное число в вычеркнутые. Оказалось, что данный подход эффективен. Алгоритм работает значительно быстрее предыдущих (для указанного количества раза в два быстрее). Но, как это обычно бывает, для увеличения скорости выполнения требуется больше памяти. Ну, такова жизнь.
Замечание 1.
Понятно, что подходы представленные на рисунках 1, 2 и 3 универсальны. Можно искать простые числа в любых промежутках. А решето Эратосфена работает от 2 до n.
Замечание 2.
Существуют и другие критерии проверки на простоту, но они не точные. Они дают точный результат, если число не простое, а если простое, то результат верен с некоторой высокой, но вероятностью. Может мы в будущем о них поговорим.
Замечание 3.
В Python есть библиотеки, где есть инструменты для проверки того, является число простым или нет. Но я всегда предпочитаю по возможности делать всё своими руками. Зачем? - спросите вы. Ну как зачем, удовольствие получить. Но в одной из статей, я с такими библиотеками всё таки вас познакомлю.
Ну и, наконец, в заключении приведу пример, усовершенствованной программы из рисунка 3 на случай, когда промежуток [a, b] произволен.
Пояснение к программе
Усовершенствование просто меняет начало промежутка на 1, если a чётное число или 2.
Статья о библиотеке primePy.
Ну, пока всё!
Пишите свои предложения и замечания, и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.
