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

Примеры простых чисел:
2, 3, 5, 7, 11, 13, ...

Составные числа (не простые):
4 (2×2), 6 (2×3), 8 (2×4), 9 (3×3), ...

Основные методы проверки

 Перебор делителей

Принцип:
Проверяем делители от 2 до √n (если делитель есть → число составное).

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

Сложность:
O(√n) — медленно для больших чисел.

 Оптимизированный перебор

Улучшения:

  • Проверяем только нечётные делители после 2.

  • Пропускаем числа, кратные 2 и 3.

def is_prime_optimized(n):
    if n <= 1:
        return False
    if n <= 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

Сложность:
O(√n / 3) — быстрее первого метода.

Детерминированные методы

 Решето Эратосфена (для поиска всех простых ≤ n)

Принцип:
Последовательно отсеиваем составные числа.

Код:

def sieve_of_eratosthenes(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            sieve[i*i : n+1 : i] = [False] * len(sieve[i*i : n+1 : i])
    return [i for i, prime in enumerate(sieve) if prime]

Сложность:
O(n log log n) — эффективно для генерации всех простых до n.