Простые числа в Python: проверка, алгоритмы и примеры кода

Введение: что такое простое число и зачем проверять простоту в Python

Простое число — это натуральное число больше 1, которое делится без остатка только на 1 и на само себя. Например, числа 2, 3, 5, 7, 11 — простые. А вот 4, 6, 8, 9 — составные, потому что у них есть другие делители.

Проверка простоты чисел — одна из самых популярных задач в программировании. Она встречается везде: от школьных олимпиад до серьёзной криптографии (шифрование данных в интернете). Python — отличный язык для таких задач: у него простой синтаксис, есть встроенные возможности для работы с большими числами, и много готовых библиотек.

В этой статье ты научишься проверять числа на простоту разными способами — от самых простых до профессиональных алгоритмов. Мы разберём все методы с примерами кода, сравним их скорость и узнаем, когда какой лучше применять.

Базовые определения и математическая теория простых чисел

Перед тем как писать код, давай разберёмся с математикой.

Основные понятия:

• Простое число — натуральное число n > 1, имеющее ровно два делителя: 1 и n
• Составное число — натуральное число n > 1, имеющее больше двух делителей
• Единица (1) — не является ни простым, ни составным числом

Важные свойства:

1. 2 — единственное чётное простое число. Все остальные простые числа — нечётные.
2. Если число n составное, то у него есть делитель d, такой что d ≤ √n (квадратный корень из n).
3. Простых чисел бесконечно много (доказал ещё Евклид).

Примеры:

• Число 17 — простое (делится только на 1 и 17)
• Число 18 — составное (делители: 1, 2, 3, 6, 9, 18)
• Число 29 — простое (проверяем делители до √29 ≈ 5.4: числа 2, 3, 4, 5 не делят 29)

Метод 1: Наивный перебор делителей — простейший подход

Самый очевидный способ проверить число на простоту — перебрать все возможные делители от 2 до n-1. Если найдётся хотя бы один делитель, число составное. Если не найдётся — простое.

Алгоритм:

1. Если n ≤ 1, возвращаем False
2. Перебираем все числа i от 2 до n-1
3. Если n делится на i без остатка, возвращаем False
4. Если ни одно число не подошло, возвращаем True

Код на Python:

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

# Примеры использования
print(is_prime_naive(7))   # True
print(is_prime_naive(10))  # False
print(is_prime_naive(13))  # True
print(is_prime_naive(1))   # False

Плюсы:

• Очень простой и понятный код
• Гарантированно правильный результат
• Подходит для обучения

Минусы:

• Очень медленный для больших чисел
• Временная сложность: O(n) — линейная

Пример медленной работы:

# Проверка числа 1000003 займёт около миллиона операций
print(is_prime_naive(1000003))  # True, но долго выполняется

Метод 2: Оптимизированный перебор до квадратного корня

Этот метод намного быстрее наивного. Главная идея: если у числа n есть делитель d больше √n, то обязательно есть парный делитель меньше √n. Поэтому достаточно проверить делители только до √n.

Дополнительные оптимизации:

1. Отдельно проверяем 2 (единственное чётное простое)
2. Проверяем только нечётные делители (3, 5, 7, 9...)
3. Используем int(n**0.5) + 1 для вычисления границы

Код на Python:

def is_prime_optimized(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # Проверяем только нечётные делители до √n
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

# Примеры использования
print(is_prime_optimized(17))      # True
print(is_prime_optimized(100))     # False
print(is_prime_optimized(97))      # True
print(is_prime_optimized(1000003)) # True (работает быстро!)

Разбор кода:

• if n == 2: return True — двойка простая, сразу возвращаем True
• if n % 2 == 0: return False — все остальные чётные числа составные
• range(3, int(n**0.5) + 1, 2) — проверяем только нечётные числа от 3 до √n
• n**0.5 — возведение в степень 0.5 это квадратный корень

Сравнение скорости:

import time

n = 1000003

# Наивный метод
start = time.time()
is_prime_naive(n)
print(f"Наивный: {time.time() - start:.4f} сек")

# Оптимизированный метод
start = time.time()
is_prime_optimized(n)
print(f"Оптимизированный: {time.time() - start:.4f} сек")

Временная сложность: O(√n) — намного быстрее линейного перебора!

Метод 3: Решето Эратосфена — нахождение всех простых до N

Если тебе нужно найти не одно простое число, а все простые числа до N, то решето Эратосфена — лучший выбор. Это древний алгоритм (придумал греческий математик Эратосфен в III веке до н.э.).

Как работает алгоритм:

1. Создаём список всех чисел от 2 до N
2. Берём первое незачёркнутое число (это простое)
3. Вычёркиваем все числа, кратные этому простому
4. Повторяем шаги 2-3, пока не закончатся числа
5. Все незачёркнутые числа — простые

Код на Python:

def sieve_of_eratosthenes(n):
    if n < 2:
        return []
    
    # Создаём список: True означает "число простое"
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            # Вычёркиваем все кратные i
            for j in range(i*i, n + 1, i):
                is_prime[j] = False
    
    # Возвращаем список простых чисел
    return [num for num in range(n + 1) if is_prime[num]]

# Примеры использования
print(sieve_of_eratosthenes(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

print(len(sieve_of_eratosthenes(1000)))
# 168 простых чисел до 1000

Разбор важных моментов:

• is_prime = [True] * (n + 1) — изначально все числа "простые"
• range(i*i, n + 1, i) — начинаем с i² (меньшие кратные уже вычеркнуты)
• Внешний цикл до √n, потому что большие делители уже учтены

Визуализация процесса для n=30:

Шаг 1: 2 — простое, вычёркиваем 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30
Шаг 2: 3 — простое, вычёркиваем 9, 15, 21, 27
Шаг 3: 5 — простое, вычёркиваем 25
Шаг 4: 7 — простое (7² = 49 > 30, останавливаемся)
Результат: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Временная сложность: O(n log log n) — очень эффективно!

Плюсы:

• Быстро находит все простые числа в диапазоне
• Простая реализация
• Отлично подходит для предварительных вычислений

Минусы:

• Требует O(n) памяти
• Неэффективен для проверки одного большого числа

primes = sieve_of_eratosthenes(100)
print(sum(primes))  # 1060

Метод 4: Решето Аткина — современная альтернатива

Решето Аткина — это современный алгоритм (2004 год), который работает немного быстрее решета Эратосфена для больших N. Он использует более сложную математику: квадратичные формы и теорию чисел.

Основная идея: Алгоритм использует специальные формулы для определения простых чисел, вместо простого вычёркивания кратных.

Упрощённый код на Python:

def sieve_of_atkin(limit):
    if limit < 2:
        return []
    
    is_prime = [False] * (limit + 1)
    is_prime[2] = is_prime[3] = True
    
    # Основной алгоритм с квадратичными формами
    for x in range(1, int(limit**0.5) + 1):
        for y in range(1, int(limit**0.5) + 1):
            n = 4*x*x + y*y
            if n <= limit and (n % 12 == 1 or n % 12 == 5):
                is_prime[n] = not is_prime[n]
            
            n = 3*x*x + y*y
            if n <= limit and n % 12 == 7:
                is_prime[n] = not is_prime[n]
            
            n = 3*x*x - y*y
            if x > y and n <= limit and n % 12 == 11:
                is_prime[n] = not is_prime[n]
    
    # Вычёркиваем квадраты простых
    for n in range(5, int(limit**0.5) + 1):
        if is_prime[n]:
            for k in range(n*n, limit + 1, n*n):
                is_prime[k] = False
    
    return [num for num in range(2, limit + 1) if is_prime[num]]

# Пример использования
print(sieve_of_atkin(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Сравнение с решетом Эратосфена:

• Скорость: Аткин немного быстрее на очень больших N (миллионы)
• Сложность кода: Аткин сложнее в понимании
• Практика: Для школьных задач Эратосфен проще и достаточно быстр

Метод 5: Тест Ферма — вероятностный подход

Все предыдущие методы были детерминированными — они точно говорят, простое число или нет. Теперь перейдём к вероятностным тестам — они работают быстро, но могут ошибаться с малой вероятностью.

Малая теорема Ферма: Если p — простое число, то для любого числа a, не кратного p, выполняется: a^(p-1) ≡ 1 (mod p)

Идея теста: Если условие не выполняется хотя бы для одного a, то число точно составное. Если выполняется для нескольких случайных a, то число вероятно простое.

Код на Python:

import random

def fermat_test(n, k=5):
    """
    n - проверяемое число
    k - количество итераций (точность теста)
    """
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # Повторяем тест k раз
    for _ in range(k):
        a = random.randint(2, n - 1)
        # Проверяем: a^(n-1) mod n == 1
        if pow(a, n - 1, n) != 1:
            return False  # Точно составное
    
    return True  # Вероятно простое

# Примеры использования
print(fermat_test(17))   # True
print(fermat_test(18))   # False
print(fermat_test(97))   # True
print(fermat_test(100))  # False

Разбор кода:

• pow(a, n-1, n) — встроенная функция Python для быстрого возведения в степень по модулю
• k=5 — количество проверок (чем больше, тем точнее)
• Используем random.randint для выбора случайного основания

Плюсы:

• Очень быстрый для больших чисел
• Простая реализация
• Хорошо работает на практике

Минусы:

• Может ошибаться (есть вероятность ложного результата)
• Существуют числа Кармайкла, которые обманывают тест

Метод 6: Тест Миллера-Рабина — надежный вероятностный алгоритм

Тест Миллера — Рабина — вероятностный полиномиальный тест простоты, который позволяет эффективно определить, является ли данное число составным. Это улучшенная версия теста Ферма, которая не обманывается числами Кармайкла.

Принцип работы: Алгоритм представляет n-1 в виде n-1 = 2^s × d (где d — нечётное), и проверяет дополнительные условия на квадратные корни.

Код на Python:

import random

def miller_rabin(n, k=5):
    """
    Тест Миллера-Рабина
    n - проверяемое число
    k - количество раундов (точность)
    """
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    
    # Представляем n-1 как 2^s * d
    s = 0
    d = n - 1
    while d % 2 == 0:
        s += 1
        d //= 2
    
    # Повторяем тест k раз
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # Составное
    
    return True  # Вероятно простое

# Примеры использования
print(miller_rabin(561))      # False (число Кармайкла!)
print(miller_rabin(17))       # True
print(miller_rabin(1000003))  # True
print(miller_rabin(1000000))  # False

Преимущества перед тестом Ферма:

• Распознаёт числа Кармайкла как составные
• Вероятность ошибки оценена величиной 1/4^k, где k — количество итераций в тесте Миллера-Рабина.
• Рекомендуемое количество итераций — пять.
• Используется в серьёзной криптографии

Проверка числа Кармайкла:

# Сравним тесты на числе 561 (число Кармайкла)
print("Тест Ферма:", fermat_test(561))        # True (ошибка!)
print("Тест Миллера-Рабина:", miller_rabin(561))  # False (правильно!)

Применение: Тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел, необходимых для создания секретных ключей (например, в шифре RSA).

Использование библиотеки sympy — готовые решения

Для практических задач не обязательно писать алгоритмы с нуля. Библиотека sympy содержит готовую функцию для проверки числа на простоту.

Установка библиотеки:

pip install sympy

Использование isprime():

from sympy import isprime

# Примеры использования
print(isprime(7))       # True
print(isprime(25))      # False
print(isprime(1000003)) # True
print(isprime(561))     # False (правильно определяет число Кармайкла!)

# Работает даже с огромными числами
big_prime = 2**89 - 1
print(isprime(big_prime))  # True

Другие полезные функции sympy:

from sympy import primerange, nextprime, prime, factorint

# Все простые в диапазоне
print(list(primerange(10, 30)))
# [11, 13, 17, 19, 23, 29]

# Следующее простое число после n
print(nextprime(100))  # 101

# n-ое простое число (нумерация с 1)
print(prime(10))  # 29 (10-е простое)

# Разложение на простые множители
print(factorint(60))  # {2: 2, 3: 1, 5: 1} = 2² × 3 × 5

Плюсы sympy:

• Высоко оптимизированные алгоритмы
• Работает с любыми большими числами
• Много дополнительных функций
• Надёжные и проверенные решения

Минусы:

• Нужно устанавливать отдельно
• Не подходит для олимпиад (где нельзя использовать сторонние библиотеки)

Особенности Python для работы с простыми числами

Python имеет несколько уникальных возможностей, которые упрощают работу с простыми числами.

1. Использование else в циклах

В Python у циклов for и while есть необычная конструкция else. Блок else выполняется, если цикл завершился нормально (без break).

def is_prime_with_else(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    else:
        # Сюда попадаем, только если не было break
        return True

print(is_prime_with_else(17))  # True

Ещё элегантнее:

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

2. Функция pow() с модулем

Python имеет встроенную функцию pow(a, b, m), которая вычисляет a^b mod m очень быстро (за логарифмическое время).

# Обычное возведение в степень (медленно для больших чисел)
result1 = (2**1000) % 1000003  # Долго вычисляется

# Быстрое возведение в степень по модулю
result2 = pow(2, 1000, 1000003)  # Мгновенно!

print(result2)  # 985184

Это критически важно для вероятностных тестов (Ферма, Миллера-Рабина), где нужно считать огромные степени.

3. Работа с большими числами

Python автоматически работает с числами любого размера (в отличие от C++ или Java).

# Огромное число (более 300 цифр!)
n = 2**1000 + 1

# Python спокойно проверяет его на простоту
print(miller_rabin(n, k=10))  # False (составное)

# Число Мерсенна
mersenne = 2**127 - 1
print(miller_rabin(mersenne, k=10))  # True (простое!)

4. Генераторы и yield

Для генерации последовательности простых чисел удобно использовать генераторы:

def prime_generator():
    """Бесконечный генератор простых чисел"""
    yield 2
    n = 3
    while True:
        if is_prime_optimized(n):
            yield n
        n += 2

# Получаем первые 10 простых чисел
gen = prime_generator()
primes = [next(gen) for _ in range(10)]
print(primes)  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Сравнительная таблица методов: производительность и сложность

Теперь сравним все методы по скорости, сложности и применению.

Практические рекомендации:

Практические примеры и задачи

Давай разберём популярные задачи с простыми числами.

Задача 1: Проверка простоты

Условие: Дано число n. Определить, простое оно или нет.

# Решение
n = int(input())
if is_prime_optimized(n):
    print("Простое")
else:
    print("Составное")

Задача 2: Количество простых в диапазоне

Условие: Подсчитать количество простых чисел от a до b.

def count_primes(a, b):
    count = 0
    for num in range(a, b + 1):
        if is_prime_optimized(num):
            count += 1
    return count

print(count_primes(10, 50))  # 11 простых чисел

Оптимизация через решето:

def count_primes_fast(a, b):
    primes = sieve_of_eratosthenes(b)
    return sum(1 for p in primes if p >= a)

print(count_primes_fast(10, 50))  # 11

Задача 3: N-ое простое число

Условие: Найти 100-ое простое число.

def nth_prime(n):
    count = 0
    num = 2
    while count < n:
        if is_prime_optimized(num):
            count += 1
            if count == n:
                return num
        num += 1

print(nth_prime(100))  # 541

Задача 4: Ближайшее простое

Условие: Найти ближайшее простое число больше n.

def next_prime(n):
    candidate = n + 1
    while True:
        if is_prime_optimized(candidate):
            return candidate
        candidate += 1

print(next_prime(100))  # 101
print(next_prime(1000)) # 1009

Задача 5: Разложение на простые множители

Условие: Разложить число n на простые множители.

def factorize(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

print(factorize(60))   # [2, 2, 3, 5]
print(factorize(100))  # [2, 2, 5, 5]
print(factorize(37))   # [37]

Генерация простых чисел в диапазоне — функции и мини-проекты

Часто нужно сгенерировать список простых чисел для дальнейшей работы.

Функция генерации простых в диапазоне

def generate_primes(start, end):
    """Генерирует все простые числа от start до end"""
    primes = []
    for num in range(start, end + 1):
        if is_prime_optimized(num):
            primes.append(num)
    return primes

# Пример
print(generate_primes(20, 50))
# [23, 29, 31, 37, 41, 43, 47]

Генератор первых N простых

def first_n_primes(n):
    """Возвращает список первых n простых чисел"""
    primes = []
    num = 2
    while len(primes) < n:
        if is_prime_optimized(num):
            primes.append(num)
        num += 1
    return primes

print(first_n_primes(20))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

Мини-проект: Таблица простых чисел

def print_prime_table(n):
    """Выводит таблицу простых чисел до n"""
    primes = sieve_of_eratosthenes(n)
    
    print(f"Простые числа от 1 до {n}:")
    print(f"Всего: {len(primes)} чисел\n")
    
    # Выводим по 10 в строке
    for i in range(0, len(primes), 10):
        row = primes[i:i+10]
        print(" ".join(f"{p:4}" for p in row))

print_prime_table(100)

Вывод:

Простые числа от 1 до 100:
Всего: 25 чисел

   2    3    5    7   11   13   17   19   23   29
  31   37   41   43   47   53   59   61   67   71
  73   79   83   89   97

Мини-проект: Простые числа-близнецы

Числа-близнецы — это пары простых чисел, отличающихся на 2 (например, 11 и 13, 17 и 19).

def find_twin_primes(limit):
    """Находит все пары простых чисел-близнецов до limit"""
    primes = sieve_of_eratosthenes(limit)
    twins = []
    
    for i in range(len(primes) - 1):
        if primes[i+1] - primes[i] == 2:
            twins.append((primes[i], primes[i+1]))
    
    return twins

twins = find_twin_primes(100)
print(f"Найдено {len(twins)} пар близнецов:")
for p1, p2 in twins:
    print(f"({p1}, {p2})")

Работа с большими числами и оптимизация

Python отлично справляется с большими числами благодаря произвольной точности целых чисел.

Проверка огромных чисел

# Число Мерсенна M_127 = 2^127 - 1
mersenne_127 = 2**127 - 1
print(f"M_127 = {mersenne_127}")
print(f"Количество цифр: {len(str(mersenne_127))}")
print(f"Простое: {miller_rabin(mersenne_127, k=10)}")

# Вывод:
# M_127 = 170141183460469231731687303715884105727
# Количество цифр: 39
# Простое: True

Оптимизация памяти для решета

Для очень больших диапазонов можно использовать битовые массивы:

def sieve_optimized(n):
    """Решето Эратосфена с оптимизацией памяти"""
    if n < 2:
        return []
    
    # Проверяем только нечётные числа (экономия памяти в 2 раза)
    size = (n - 1) // 2
    is_prime = [True] * size
    
    for i in range(int(n**0.5) // 2):
        if is_prime[i]:
            p = 2 * i + 3
            # Вычёркиваем кратные p
            for j in range((p*p - 3) // 2, size, p):
                is_prime[j] = False
    
    # Собираем результат
    primes = [2] + [2*i + 3 for i in range(size) if is_prime[i]]
    return primes

# Генерация миллиона простых чисел
primes = sieve_optimized(1000000)
print(f"Найдено {len(primes)} простых чисел до 1000000")
# Найдено 78498 простых чисел

Измерение производительности

import time

def benchmark_methods(n):
    """Сравнение скорости разных методов"""
    methods = {
        "Перебор до √n": is_prime_optimized,
        "Тест Ферма": fermat_test,
        "Тест Миллера-Рабина": miller_rabin,
    }
    
    print(f"Проверка числа {n}:\n")
    
    for name, func in methods.items():
        start = time.time()
        result = func(n)
        elapsed = time.time() - start
        print(f"{name:25} {elapsed:.6f} сек - {result}")

# Тестируем на большом числе
benchmark_methods(1000000007)

Числа Кармайкла и ограничения вероятностных тестов

Числа Кармайкла — это особые составные числа, которые обманывают тест Ферма.

Наименьшее из них — 561, такие числа не позволяют применять тест Ферма как универсальное средство проверки простоты.

Примеры чисел Кармайкла

Первые несколько чисел Кармайкла: 561, 1105, 1729, 2465, 2821, 6601, 8911...

# Разложение 561 на множители
print(factorize(561))  # [3, 11, 17]
# 561 = 3 × 11 × 17

# Проверка разными методами
print("561 тестом Ферма:", fermat_test(561, k=10))      # True (ошибка!)
print("561 тестом Миллера-Рабина:", miller_rabin(561))  # False (правильно!)
print("561 sympy:", isprime(561))                       # False (правильно!)

Почему Миллер-Рабин лучше

Тест Соловея — Штрассена и тест Миллера-Рабина распознают числа Кармайкла как составные. Тест Миллера-Рабина использует дополнительные проверки квадратных корней из 1 по модулю n, что позволяет обнаружить составные числа даже если они проходят тест Ферма.

Тестирование нескольких чисел Кармайкла

carmichael_numbers = [561, 1105, 1729, 2465, 2821, 6601, 8911]

print("Число  | Ферма | Миллер-Рабин")
print("-" * 35)

for n in carmichael_numbers:
    ferma = fermat_test(n, k=5)
    miller = miller_rabin(n, k=5)
    print(f"{n:6} | {str(ferma):5} | {str(miller):5}")

Результат:

Число  | Ферма | Миллер-Рабин
-----------------------------------
   561 | True  | False
  1105 | True  | False
  1729 | True  | False
  2465 | True  | False
  2821 | True  | False
  6601 | True  | False
  8911 | True  | False

Частые ошибки при проверке простоты

Разберём типичные ошибки, которые допускают начинающие программисты.

Ошибка 1: Забывать про 1 и 2

Неправильно:

def is_prime_wrong(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

print(is_prime_wrong(1))  # True - ОШИБКА! 1 не простое

Правильно:

def is_prime_correct(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    # остальной код...

Ошибка 2: Не учитывать чётные числа

Неэффективно:

# Проверяем все делители
for i in range(2, int(n**0.5) + 1):
    if n % i == 0:
        return False

Эффективнее:

# Отдельно проверяем 2, потом только нечётные
if n % 2 == 0:
    return False
for i in range(3, int(n**0.5) + 1, 2):
    if n % i == 0:
        return False

Ошибка 3: Неправильная граница цикла

Неправильно:

# Граница без +1
for i in range(2, int(n**0.5)):  # Может пропустить делитель!

Правильно:

for i in range(2, int(n**0.5) + 1):  # +1 обязательно!

Пример проблемы:

n = 49  # 49 = 7 × 7
# int(49**0.5) = 7
# range(2, 7) даст [2, 3, 4, 5, 6] - без 7!
# range(2, 8) даст [2, 3, 4, 5, 6, 7] - правильно

Ошибка 4: Использование теста Ферма для критичных задач

Неправильно:

# В криптографии
def generate_rsa_prime():
    while True:
        p = random_large_number()
        if fermat_test(p):  # ОПАСНО!
            return p

Правильно:

# В криптографии
def generate_rsa_prime():
    while True:
        p = random_large_number()
        if miller_rabin(p, k=20):  # Надёжно!
            return p

Ошибка 5: Не использовать pow() с модулем

Неправильно (медленно):

result = (a ** (n-1)) % n  # Сначала считает огромное число

Правильно (быстро):

result = pow(a, n-1, n)  # Считает сразу по модулю

Заключение и рекомендации по выбору метода

Ты изучил множество способов работы с простыми числами в Python. Давай подведём итоги.

Краткие рекомендации

Для учёбы и понимания:

• Начни с наивного перебора — понятный базовый алгоритм
• Переходи к оптимизированному перебору до √n — универсальный метод
• Изучи решето Эратосфена — классика алгоритмов

Для олимпиад:

• Одно число: перебор до √n с оптимизациями
• Диапазон чисел: решето Эратосфена
• Большие числа: тест Миллера-Рабина

Для реальных проектов:

• Используй sympy.isprime() — проверено и оптимизировано
• Для критичных приложений: Миллер-Рабин с k ≥ 20

Алгоритм выбора метода

if можешь_использовать_библиотеки:
    use sympy.isprime()
elif нужно_проверить_один_раз:
    if число < 10**12:
        use перебор_до_корня()
    else:
        use миллер_рабин(k=10)
elif нужны_все_простые_в_диапазоне:
    if диапазон < 10**7:
        use решето_эратосфена()
    else:
        use решето_аткина()
elif криптография:
    use миллер_рабин(k=20)

Что запомнить

Теперь ты знаешь всё необходимое для работы с простыми числами в Python! Практикуйся, решай задачи, и скоро эти алгоритмы станут для тебя простыми и понятными. Удачи в программировании!