Можешь ли ты написать функцию на Python, которая определяет, является ли заданное число простым, и объяснить логику своей реализации?

Question

Accepted Answer

## Обзор

**Простое число** — это любое целое число, больше 1, которое не имеет делителей, кроме 1 и самого себя. Вот чистая и эффективная реализация:

```python
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True
```

## Разбор логики

- **Базовый случай:** Любое число меньше 2 *сразу же* отклоняется как непростое
- **Диапазон цикла:** Мы проверяем делители только от `2` до **квадратного корня** числа `n`
- **Проверка делимости:** Если `n % i == 0`, делитель найден и мы возвращаем `False`
- **Результат по умолчанию:** Если делитель не найден, функция возвращает `True`

## Зачем использовать квадратный корень?

Это ключевая *оптимизация*. Если у числа `n` есть делитель больше его квадратного корня, то у него обязательно есть соответствующий делитель *меньше* квадратного корня. Поэтому проверки до `int(n**0.5) + 1` достаточно, чтобы избежать лишних итераций.

## Сложность

- **Временная сложность:** `O(√n)` — значительно быстрее, чем наивный подход `O(n)`
- **Пространственная сложность:** `O(1)` — дополнительная память не используется

## Пример использования

```python
print(is_prime(7))   # True
print(is_prime(10))  # False
print(is_prime(1))   # False
```

Можешь ли ты написать функцию на Python, которая определяет, является ли заданное число простым, и объяснить логику своей реализации?

Ответ

Обзор

Разбор логики

Зачем использовать квадратный корень?

Сложность

Пример использования

Проверочные вопросы

Помогите улучшить этот вопрос

Обсуждение