Как проверить является ли число простым?

Для начала вспомним определение: простое число - это натуральное число, имеющее ровно два различных натуральных делителя.

Поиск таких чисел это одна из самых часто встречаемых задач в алгоритмах программирования.

И так, начнем:

Это самый простой и неоптимизированный алгоритм, работает и слава Богу!)

Полностью аналогичный пример, только для подсчета кол-ва делителей мы используем списочное выражение. Заполняем список делителями и если длина списка len() равна 2 (то есть ровно два делителя нашлось), то выводим истину.

Мы пробегаем диапазон от 2-х до самого числа (не включая его) и если найдется какой-либо другой делитель, то число не является простым.

for i in range(2, int(x**0.5) + 1)

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

Четверты пример самый коротки, но не самый простой! Получая число в функцию для проверки мы проверяем, что оно больше нуля, а дальше проверяем через all() , что для всех x условие x % i != 0 является истинным и только в таком случае возвращаем True.

Задача на поиск простого числа будет преследовать нас в 25 номере и в ряди других примеров, хоть и не часто. Делитесь своими вариантами поиска простых чисел в комментариях!

📎 Ссылка на код github