PrepBro
← Назад к вопросам

Проверка простого числа

1.0 Junior🔥 261 комментариев
#Python Core

Условие

Напишите функцию, которая проверяет, является ли число простым.

Простое число — это натуральное число больше 1, которое делится только на 1 и на само себя.

Пример

7 → True (делится только на 1 и 7) 12 → False (делится на 1, 2, 3, 4, 6, 12) 2 → True 1 → False

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Проверка простого числа: полный разбор

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

Решение 1: Базовый подход (O(n))

def is_prime_basic(n: int) -> bool:
    """
    Проверяет, является ли число простым (базовый подход).
    
    Args:
        n: Проверяемое число
    
    Returns:
        True, если число простое, иначе False
    """
    # Числа меньше 2 не являются простыми
    if n < 2:
        return False
    
    # 2 - единственное чётное простое число
    if n == 2:
        return True
    
    # Все чётные числа (кроме 2) не простые
    if n % 2 == 0:
        return False
    
    # Проверяем делители от 3 до n-1
    for i in range(3, n):
        if n % i == 0:
            return False  # Нашли делитель, число не простое
    
    return True

# Примеры
print(is_prime_basic(7))    # True
print(is_prime_basic(12))   # False
print(is_prime_basic(2))    # True
print(is_prime_basic(1))    # False
print(is_prime_basic(97))   # True

# Проблема: неэффективно для больших чисел
# Для числа 1000000 нужно проверить ~1000000 делителей

Решение 2: Оптимизированный подход (O(√n)) ⭐ РЕКОМЕНДУЕТСЯ

Ключевое наблюдение: если n = a × b, то одно из чисел (a или b) ≤ √n.

import math

def is_prime(n: int) -> bool:
    """
    Оптимизированная проверка простоты числа.
    Проверяет делители только до sqrt(n).
    
    Сложность: O(√n)
    """
    # Числа меньше 2 не являются простыми
    if n < 2:
        return False
    
    # 2 - единственное чётное простое число
    if n == 2:
        return True
    
    # Все чётные числа не простые
    if n % 2 == 0:
        return False
    
    # Проверяем нечётные делители до sqrt(n)
    # Если число имеет делитель, он будет <= sqrt(n)
    limit = int(math.sqrt(n)) + 1
    
    for i in range(3, limit, 2):
        if n % i == 0:
            return False
    
    return True

# Примеры
print(is_prime(7))      # True
print(is_prime(12))     # False
print(is_prime(2))      # True
print(is_prime(1))      # False
print(is_prime(97))     # True
print(is_prime(100))    # False
print(is_prime(101))    # True
print(is_prime(1000000007))  # True

# Для числа 1000000007:
# Вместо проверки 1 млрд делителей, проверяем ~31623

Решение 3: С использованием генератора (Pythonic)

def is_prime_generator(n: int) -> bool:
    """
    Проверка с использованием любого (any) и генератора.
    Более функциональный стиль Python.
    """
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # Проверяем только нечётные делители
    # all() вернёт True, если ни одно число не делит n нацело
    limit = int(n ** 0.5) + 1
    return all(n % i != 0 for i in range(3, limit, 2))

print(is_prime_generator(7))    # True
print(is_prime_generator(12))   # False

Решение 4: С типизацией и документацией

from typing import TypeVar

Number = TypeVar('Number', int, float)

def is_prime_typed(n: int) -> bool:
    """
    Проверяет, является ли целое число простым.
    
    Используется алгоритм "Пробное деление" с оптимизацией O(√n).
    
    Args:
        n: Целое число для проверки
    
    Returns:
        True, если число простое, False иначе
    
    Raises:
        TypeError: Если n не является целым числом
    
    Examples:
        >>> is_prime_typed(2)
        True
        >>> is_prime_typed(7)
        True
        >>> is_prime_typed(12)
        False
        >>> is_prime_typed(1)
        False
    """
    if not isinstance(n, int):
        raise TypeError(f"Expected int, got {type(n).__name__}")
    
    if n < 2:
        return False
    
    if n == 2:
        return True
    
    if n % 2 == 0:
        return False
    
    limit = int(n ** 0.5) + 1
    
    for divisor in range(3, limit, 2):
        if n % divisor == 0:
            return False
    
    return True

# Тестирование
try:
    print(is_prime_typed(7))      # True
    print(is_prime_typed(12))     # False
    print(is_prime_typed("seven"))  # TypeError
except TypeError as e:
    print(f"Error: {e}")

Решение 5: С кэшированием для множественных проверок

from functools import lru_cache

@lru_cache(maxsize=128)
def is_prime_cached(n: int) -> bool:
    """
    Оптимизированная проверка с кэшированием результатов.
    Полезна при проверке одних и тех же чисел несколько раз.
    """
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    limit = int(n ** 0.5) + 1
    return all(n % i != 0 for i in range(3, limit, 2))

# При повторном вызове результат возьмётся из кэша
print(is_prime_cached(7))      # Вычисляется
print(is_prime_cached(7))      # Из кэша
print(is_prime_cached(97))     # Вычисляется

Сравнение производительности

import time
import math

def benchmark_is_prime():
    """
    Сравнивает производительность разных подходов.
    """
    test_number = 1000000007  # Большое простое число
    
    # Базовый подход
    start = time.time()
    result1 = is_prime_basic(test_number)
    time_basic = time.time() - start
    print(f"Базовый подход: {time_basic:.6f}с")
    
    # Оптимизированный подход
    start = time.time()
    result2 = is_prime(test_number)
    time_optimized = time.time() - start
    print(f"Оптимизированный подход: {time_optimized:.6f}с")
    
    # Соотношение
    speedup = time_basic / time_optimized
    print(f"Ускорение в {speedup:.1f} раз")
    
    assert result1 == result2 == True

# benchmark_is_prime()
# Примерный результат:
# Базовый подход: 0.450000с
# Оптимизированный подход: 0.000030с
# Ускорение в 15000 раз

Тестирование

def test_is_prime():
    """
    Comprehensive тестирование функции is_prime.
    """
    # Граничные случаи
    assert is_prime(0) == False, "0 не простое"
    assert is_prime(1) == False, "1 не простое"
    assert is_prime(-5) == False, "Отрицательные числа не простые"
    
    # Малые простые числа
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for num in small_primes:
        assert is_prime(num) == True, f"{num} должно быть простым"
    
    # Не простые числа
    non_primes = [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20]
    for num in non_primes:
        assert is_prime(num) == False, f"{num} не должно быть простым"
    
    # Известные большие простые числа
    large_primes = [97, 101, 1009, 10007, 100003, 1000003]
    for num in large_primes:
        assert is_prime(num) == True, f"{num} должно быть простым"
    
    # Квадраты простых чисел (не простые)
    for p in [2, 3, 5, 7, 11]:
        assert is_prime(p * p) == False, f"{p*p} не должно быть простым"
    
    print("✓ Все тесты пройдены!")

test_is_prime()

Трюки и оптимизации

# Трюк 1: Проверка делимости на 2 и 3
def is_prime_optimized(n: int) -> bool:
    """
    Ещё более оптимизированный подход.
    Все простые числа > 3 имеют вид 6k ± 1.
    """
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    # Проверяем делители вида 6k ± 1
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    
    return True

# Трюк 2: Использование битовых операций (для очень больших объёмов)
# Но обычно не нужно в Python

print(is_prime_optimized(7))    # True
print(is_prime_optimized(12))   # False
print(is_prime_optimized(97))   # True

Сложность алгоритмов

ПодходВременная сложностьПространственнаяПримечание
БазовыйO(n)O(1)Слишком медленно для больших чисел
ОптимизированныйO(√n)O(1)Рекомендуется
С кэшемO(√n) первый разO(k)k - число кэшированных значений
Решето ЭратосфенаO(n log log n)O(n)Для проверки множества чисел

Практический совет

# Используй это решение в production
def is_prime(n: int) -> bool:
    """Быстрая и надёжная проверка простоты числа."""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    limit = int(n ** 0.5) + 1
    return all(n % i != 0 for i in range(3, limit, 2))

# Это правильный баланс между:
# - Простотой и читаемостью
# - Эффективностью (O(√n))
# - Питоничностью (all() с генератором)
Проверка простого числа | PrepBro