Возвращаемся к Python 💪 Сегодня классика классик, которую при этом заваливают чаще, чем кажется.
Задачка с интервью в 🛒. Условие:
Написать функцию, определяющую, является ли целое положительное число простым.
➡️ Что такое простое число?
Простое число - это натуральное число больше 1, у которого ровно два делителя: единица и оно само. То есть 7 - простое (делится только на 1 и 7), а 9 - нет (делится еще и на 3).
Тут сразу два кейса, на которых люди путаются:
❗️Единица - НЕ простое число
У нее всего один делитель - она сама. Определение требует ровно двух.
❗️Двойка - простое
Классическая ошибка - написать "если число четное, то не простое" и словить False на двойке 🤓
➡️ Уточняем условие
Нам сказали, что на вход придет целое положительное число. Формально это значит n ≥ 1, но правильным тоном будет спросить:
• А ноль или отрицательные точно не прилетят? Если да - падаем с ошибкой или возвращаем False?
• А если прилетит не int?
Обычно говорят "не парься, вход валидный". Но вопрос показывает, что вы думаете о границах 🥁
➡️ Наивное решение
Самое простое - перебрать всех кандидатов до n-1:
• Если n < 2 - возвращаем False (закрывает и 0/1, и отрицательные, если все-таки просочатся)
• Иначе - проверяем делители
def is_prime(n: int) -> bool:
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
Но тут мы проходим все числа от 2 до n и на числе типа 10⁹ будем сидеть очень долго. Вас обязательно спросят "а можно быстрее?" 🙃
➡️ Надо проверять не до n, а до √n
Докажем от противного. Пусть n - составное (= не простое), то есть n = a · b, где оба множителя больше 1. Предположим, что оба множителя больше √n. Тогда:
a · b > √n · √n = n
Но a · b = n. Получили n > n - противоречие ❌
Значит, хотя бы один из множителей ≤ √n. А раз так - если у числа вообще есть делитель, мы гарантированно найдем его до корня ✌️
➡️ Корень - включительно или нет?
Корень нужно включать!
Смотрим на n = 25. √25 = 5. Если мы проверим только до 4 включительно, мы пропустим единственный нетривиальный делитель.
➡️ Кодим 🥰
def is_prime(n: int) -> bool:
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
Для n = 10⁹ теперь ~31 тысяча итераций вместо миллиарда !! 🔥
❗️Я специально написала условие как i * i <= n, а не i <= n**0.5
Почему так надежнее: n**0.5 и math.sqrt() работают с числами с плавающей точкой. На больших n может вылезти погрешность вида 4.999... вместо 5.0, int() ее обрежет до 4, и мы получим ошибку на единицу.
➡️ Что можно оптимизировать?
• Оптимизация №1: пропускаем четные
• Оптимизация №2: трюк 6k ± 1
Трюк 6k ± 1: Любое целое число можно записать в одном из шести видов: 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5. Смотрим, кто из них может быть простым:
6k → делится на 6
6k+2 и 6k+4 → делятся на 2
6k+3 → делится на 3
Остаются только 6k+1 и 6k+5 (последнее удобнее записать как 6k−1). То есть все простые числа, начиная с 5, имеют вид 6k ± 1 ✌️ А значит можно прыгать сразу через 6, проверяя по два кандидата за шаг:
def is_prime(n: int) -> bool:
if n < 2:
return False
if n in (2, 3):
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
На собесах обычно производит впечатление. Но если сомневаетесь, что воспроизведете без ошибок - не рискуйте !!
❗️А если просят найти ВСЕ простые до n?
Запускать цикл до n, где вы проверяете is_prime(i) для каждого числа, - слишком неоптимально. Правильный ответ - решето Эратосфена.
Но это уже задачка со звездочкой 💫, и я ее на собесах у аналитиков не видела. Если интересно - погуглите, штука прикольная 🥰
————
Ну что, смогли бы решить сами? 🥁 Жду ваших 🔥
Предыдущие разборы:
• Разбор задачек с собеседований vol. 5
• Разбор задачек с собеседований vol. 6
• Разбор задачек с собеседований vol. 7