Разбор задачек с собеседований vol. 8 🍏
Возвращаемся к 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
Возвращаемся к 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