Python: простые числа. Два способа проверки

Программирование тесно переплетено с математикой, и как бы этого не хотелось делать некоторым, вспоминать математику, если она забыта, придется. Понятие простых чисел так же изучается в школьном курсе математики, и напомнить его считаю не лишним. Если говорить "человеческим" языком, простым называют то натуральное число, которое без остатка делится только на единицу и само на себя. Чисел таких довольно много:

И это только начало!

Изображение 0fjd125gk87 с сайта Pixabay Давайте построим алгоритм на языке программирования Python, который будет определять является ли число, введенное пользователем, простым.

Сделать это довольно просто:

Изображение автора Действительно, мы запрашиваем у пользователя число, которое необходимо проверить, инициализируем переменную, куда будем "складывать" все имеющиеся делители. Делители ищем в цикле, который будет перебирать числа от 1 (на ноль делить нельзя) до самого числа, введенного пользователем. Если число делителей будет равно 2, то выводим сообщение о том, что число простое. В остальных же случаях число составное. Все согласно определению простого числа. Но давайте подумаем, получится ли у нас оптимизировать процесс проверки?

Да, это можно сделать гораздо проще.

Изображение автора Во-первых, проверять деление числа на 1, как и деление числа на само себя, смысла не имеет, так как все натуральные числа делятся и на 1 и на само себя без остатка. Более того, минимальный результат деления без остатка, который мы можем найти в принципе, это 2, поэтому мы смело можем сократить диапазон поиска делителей вдвое, не забыв прибавить к этому выражению единицу, так как функция range() не использует последнее число диапазона в скобках. К тому же, как только мы находим единственный делитель, кроме 1 и самого числа, мы можем с чистой совестью прервать цикл и сделать вывод, что число составное. И только если число простое, цикл совершит user_num / 2 итераций, что значительно повышает производительность изначального кода с первого изображения. (Изображение для мобильной версии Ralph Nas с сайта Pixabay)