Напишите функцию is_prime(n) на Python, которая возвращает True, если число $n$ простое, и False в противном случае. Подумайте об эффективности.
Делители проверяем до √n
Простое число — натуральное число $n > 1$, делителями которого являются только 1 и само $n$.
Достаточно проверять делители от 2 до $\sqrt{n}$: если у числа есть делитель больше $\sqrt{n}$, то парный ему делитель меньше $\sqrt{n}$ уже был бы найден.
def is_prime(n: int) -> bool:
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2 # пропускаем чётные
return True
print(is_prime(17)) # True
print(is_prime(100)) # False
print(is_prime(2)) # True
Сложность: $O(\sqrt{n})$. Для $n=10^9$ это ~31623 итерации — мгновенно.
Razbery — про разбор, не про списывание. Объяснение обязательно.