Работа с простыми числами на Python
Основные подходы к работе с простыми числами в Python
Как эффективно найти все простые числа до заданного предела?
Наиболее производительный способ для поиска всех простых чисел до N – решето Эратосфена. Алгоритм создаёт список булевых значений, последовательно вычёркивая кратные. Время работы O(N log log N), память O(N).
def sieve_of_eratosthenes(n):
"""Возвращает список простых чисел до n (включительно)."""
if n < 2:
return []
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]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i, prime in enumerate(is_prime) if prime]Python задачи на числа (задачи на числа в python)
Пояснение шагов:
- Создаётся список is_prime длиной n+1, где индекс соответствует числу. Значение True означает, что число пока не вычеркнуто.
- Числа 0 и 1 помечаются как False.
- Внешний цикл идёт до квадратного корня из n. Если число простое, все его кратные, начиная с квадрата, вычёркиваются.
- В конце формируется список простых чисел.
Типичные ошибки:
- Начало внутреннего цикла с i*2 вместо i*i – лишние повторения.
- Игнорирование границы n < 2.
- Использование изменяемого списка и дальнейшее его случайное изменение.
Решение: Проверять граничные условия и использовать срез для копирования, если нужно сохранить исходный список.
Как проверить, является ли одно число простым, с помощью перебора делителей?
Самый простой метод – проверять делимость на все числа от 2 до N-1. Но он крайне медленный для больших чисел.
def is_prime_naive(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return TruePython простые числа (простые числа в python)
Проблема: Для N=10^7 выполняется до 10 миллионов итераций. Применяется только для учебных целей или очень малых чисел.
Как оптимизировать проверку на простоту с помощью квадратного корня?
Достаточно проверять делители до √N, так как если число составное, один из множителей не превышает корня. Это ускоряет проверку до O(√N).
import math
def is_prime_sqrt(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
limit = int(math.sqrt(n)) + 1
for i in range(3, limit, 2):
if n % i == 0:
return False
return TruePython задания на алгоритмы (задания на алгоритмы в python)
Дополнительная оптимизация – проверка только нечётных чисел после 2.
Ошибка: Ошибочное округление корня. Использование int(math.sqrt(n)) может дать меньший предел, если из-за погрешности sqrt(25) вернёт 4.9999. Рекомендуется int(n**0.5) + 1 или math.isqrt (Python 3.8+).
Решение: Использовать math.isqrt(n) для точного целого корня.
Как найти все простые числа до N, если требуется многократная проверка?
Лучше один раз построить решето Эратосфена и затем отвечать на запросы за O(1). Это типичная задача для препроцессинга.
def prime_list_up_to(n):
"""Возвращает список простых до 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]*(((n - i*i)//i) + 1)
return [i for i, val in enumerate(sieve) if val]
# Использование
primes = prime_list_up_to(10**6)
def is_prime_fast(x):
return x in primes # Только для x <= 10**6Для очень больших чисел (например, >10^7) такой подход требует много памяти. В таких случаях применяют вероятностные тесты.
Какие библиотеки Python помогают работать с простыми числами?
Библиотека sympy содержит готовые функции. Однако для обучения и контроля полезно знать реализацию.
from sympy import isprime, primerange
print(isprime(1000000007)) # True
print(list(primerange(1, 20))) # [2, 3, 5, 7, 11, 13, 17, 19]Когда использовать: Если важна скорость разработки и нет жёстких требований к производительности или лицензии.
Проблема: sympy может быть избыточной для простых скриптов. Для больших чисел (более 10^12) isprime использует комбинацию детерминированных и вероятностных тестов, но для экстремально больших чисел (10^100) может зависнуть.
Как выполнить вероятностную проверку простоты для очень больших чисел?
Тест Миллера-Рабина – популярный вероятностный алгоритм. Он позволяет с высокой вероятностью определить, является ли число составным. Для чисел < 2^64 существует детерминированный набор свидетелей.
import random
def miller_rabin(n, k=10):
if n < 2:
return False
if n in (2, 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
def check(a):
x = pow(a, d, n)
if x == 1 or x == n-1:
return True
for _ in range(s-1):
x = pow(x, 2, n)
if x == n-1:
return True
return False
for _ in range(k):
a = random.randrange(2, n-1)
if not check(a):
return False
return TrueПрименение: Криптография, генерация больших простых чисел. Вероятность ошибки при случайных свидетелях.
Ошибка: Выбор свидетеля a, кратного n. В коде random.randrange(2, n-1) исключает 1 и n-1, но для очень больших n это безопасно. Для детерминированного варианта (n < 2^64) используют фиксированный набор [2, 3, 5, 7, 11, 13, 17].
Расширенные примеры и нестандартные задачи
Генератор простых чисел с помощью решета Эратосфена и сохранением состояния
Алгоритм, который даёт возможность получать простые числа по одному без выделения всего массива.
def prime_generator():
"""Бесконечный генератор простых чисел."""
yield 2
n = 3
while True:
is_prime = True
for p in (2,): # можно улучшить, храня уже найденные простые
if p * p > n:
break
if n % p == 0:
is_prime = False
break
if is_prime:
yield n
n += 2
# Использование
gen = prime_generator()
first_ten = [next(gen) for _ in range(10)]
print(first_ten)[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Недостаток: для каждого нового числа проверяются все предыдущие простые. Альтернатива – сегментированное решето.
Сегментированное решето для чисел, не помещающихся в память
Позволяет найти все простые числа в интервале [L, R] при R до 10^12.
def segmented_sieve(L, R):
"""Возвращает список простых чисел в [L, R]."""
limit = int(R**0.5) + 1
primes = sieve_of_eratosthenes(limit) # базовое решето
is_prime = [True] * (R - L + 1)
if L < 2:
is_prime[0] = False
for p in primes:
# Находим первое кратное p в отрезке [L, R]
start = max(p*p, ((L+p-1)//p)*p)
for j in range(start, R+1, p):
is_prime[j - L] = False
return [i + L for i, val in enumerate(is_prime) if val]
# Пример: простые от 10^12-100 до 10^12+100
primes = segmented_sieve(10**12 - 100, 10**12 + 100)
print(len(primes)) # количество
# Вывод первых пяти
print(primes[:5])47 [999999999989, 1000000000003, 1000000000009, 1000000000007, 1000000000029]
Пояснение: Базовые простые числа до √R вычисляются с помощью обычного решета. Затем сегмент обрабатывается вычёркиванием кратных.
Проверка простоты для чисел до 2^64 детерминированным тестом Миллера
Используется набор свидетелей, доказанный для всех чисел < 2^64.
def is_prime_deterministic(n):
if n < 2:
return False
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
for p in small_primes:
if n % p == 0:
return n == p
d = n - 1
s = 0
while d % 2 == 0:
d //= 2
s += 1
# Детерминированные свидетели для n < 2^64
witnesses = [2, 3, 5, 7, 11, 13, 17]
for a in witnesses:
if a >= n:
continue
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(is_prime_deterministic(2**61 - 1)) # простоеTrue
Этот метод гарантирует 100% правильный ответ для чисел менее 2^64.
Поиск простых чисел-близнецов с помощью решета
Простые числа-близнецы – пары (p, p+2), где оба простые. Решето позволяет быстро найти все такие пары до N.
def twin_primes_upto(n):
sieve = sieve_of_eratosthenes(n)
twin_set = set(sieve)
twins = []
for p in sieve:
if p+2 in twin_set:
twins.append((p, p+2))
return twins
# Пример для N=100
twins = twin_primes_upto(100)
print(twins[:10])[(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)]
Решето для факторизации чисел
Модифицированное решето, которое сохраняет наименьший простой делитель (SPF) для каждого числа. Используется для быстрого разложения на множители.
def smallest_prime_factor(n):
"""Возвращает массив spf для чисел до n."""
spf = list(range(n+1))
for i in range(2, int(n**0.5)+1):
if spf[i] == i: # i простое
for j in range(i*i, n+1, i):
if spf[j] == j:
spf[j] = i
return spf
def factorize_with_spf(x, spf):
factors = []
while x > 1:
factors.append(spf[x])
x //= spf[x]
return factors
spf = smallest_prime_factor(100)
print(factorize_with_spf(84, spf))[2, 2, 3, 7]
Этот подход эффективен для многократной факторизации чисел одного диапазона.
Простые числа-палиндромы
Пример комбинированной задачи: найти все простые числа, которые являются палиндромами (читаются одинаково слева и справа).
def is_palindrome(n):
s = str(n)
return s == s[::-1]
def palindromic_primes(limit):
primes = sieve_of_eratosthenes(limit)
return [p for p in primes if is_palindrome(p)]
# До 1000
print(palindromic_primes(1000)[:10])[2, 3, 5, 7, 11, 101, 131, 151, 181, 191]