Программы для нахождения простых чисел на Python
Программы поиска простых чисел на Python
Поиск простых чисел (чисел, которые делятся только на 1 и на себя) - классическая задача программирования. В зависимости от требуемого диапазона и производительности применяются разные подходы. Рассмотрим несколько вариантов, от простейших до оптимальных, с примерами кода и разбором типичных ошибок.
Основное эффективное решение: решето Эратосфена
Как найти все простые числа до заданного числа N максимально быстро?
Решето Эратосфена позволяет найти все простые числа до N за время O(n log log n). Идея: создаётся список булевых значений (True - простое), затем последовательно вычёркиваются числа, кратные найденным простым.
def sieve_eratosthenes(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]
print(sieve_eratosthenes(30))задача a b python (решение задачи с переменными a и b в python)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
программа простых чисел в python (программа поиска простых чисел на python)
Распространенная ошибка: начинать вычеркивание с i*2, а не с i*i. Это приводит к многократному вычеркиванию одних и тех же чисел и падению производительности. Решение: стартовать с i*i, так как все меньшие составные числа уже вычеркнуты.
Проблемы с памятью: при N > 10^7 список bool может занимать много памяти. Выход - использовать битовые массивы (например, array('b') или bitarray).
Как улучшить решето для экономии памяти?
Можно хранить только нечётные числа, уменьшив размер вдвое:
def sieve_odd(n):
if n < 2:
return []
is_prime = [True] * ((n - 1) // 2 + 1)
for i in range(3, int(n ** 0.5) + 1, 2):
if is_prime[i // 2]:
start = i * i
step = i * 2
for j in range(start, n + 1, step):
is_prime[j // 2] = False
return [2] + [i * 2 + 1 for i, p in enumerate(is_prime[1:], 1) if p]Вариант 1: Перебор делителей (наивный)
Как проверить, является ли число простым, без использования списков?
Самый простой способ: проверить, делится ли число на любое целое от 2 до n-1. Если делителей нет - число простое.
def is_prime_naive(n):
if n < 2:
return False
for d in range(2, n):
if n % d == 0:
return False
return True
print(is_prime_naive(17))True
Проблема: очень медленно для больших n (O(n)). Для n = 10^9 потребует миллиарда итераций. Решение - использовать улучшенный перебор (см. далее).
Вариант 2: Улучшенный перебор до квадратного корня
Как ускорить проверку простоты, уменьшив количество делителей?
Так как любой составной делитель n не превосходит sqrt(n), достаточно проверить делители до √n. Дополнительно можно проверять только нечётные делители после 2.
def is_prime_sqrt(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
print(is_prime_sqrt(97))True
Ошибка: забыть проверить чётность отдельно - тогда будет лишняя итерация для i=2. Решение: явно обработать случай 2 и начинать с 3 с шагом 2.
Вариант 3: Использование библиотеки sympy
Как получить готовую функцию для проверки простоты без написания алгоритма?
Библиотека sympy содержит функцию isprime, основанную на тесте Миллера-Рабина для больших чисел и решето для малых.
from sympy import isprime
print(isprime(1000000007))True
Примечание: sympy не всегда установлена по умолчанию; требуется pip install sympy. Для очень больших чисел (сотни цифр) тест может занять заметное время.
Вариант 4: Генератор простых чисел с помощью решета по сегментам
Как найти простые числа в заданном диапазоне [L, R] при R-L большом и R огромном?
Сегментированное решето применяет алгоритм Эратосфена только к части чисел, используя малые простые числа для вычёркивания сегмента.
def segmented_sieve(l, r):
if l < 2:
l = 2
limit = int(r ** 0.5) + 1
small_primes = sieve_eratosthenes(limit)
is_prime_seg = [True] * (r - l + 1)
for p in small_primes:
# Найти первое кратное p в сегменте
start = max(p * p, ((l + p - 1) // p) * p)
for j in range(start, r + 1, p):
is_prime_seg[j - l] = False
return [i + l for i, v in enumerate(is_prime_seg) if v]
print(segmented_sieve(100, 150))[101, 103, 107, 109, 113, 127, 131, 137, 139, 149]
Типичная ошибка: неверный расчёт start - если p*p меньше l, нужно начинать с первого кратного в сегменте, иначе начинать с p*p. Иначе числа меньше p*p могут быть вычеркнуты неправильно.
Вариант 5: Вероятностный тест Миллера-Рабина
Как проверить простоту очень больших чисел (сотни цифр) быстро, допуская ничтожную вероятность ошибки?
Тест Миллера-Рабина вероятностный, но его можно сделать детерминированным для чисел до определённых границ.
import random
def miller_rabin(n, k=5):
if n < 2:
return False
if n in (2, 3):
return True
if n % 2 == 0:
return False
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
def witness(a):
x = pow(a, d, n)
if x == 1 or x == n - 1:
return True
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
return True
return False
for _ in range(k):
a = random.randint(2, n - 2)
if not witness(a):
return False
return True
print(miller_rabin(1000000007))True
Ошибка: при n = 1 или 2 алгоритм может вернуть неверный результат без специальных проверок. Решение: добавить обработку малых чисел.
Расширенные примеры: сравнение и оптимизация алгоритмов
1. Сравнение времени выполнения наивного и улучшенного перебора
import time
def is_prime_naive(n):
for d in range(2, n):
if n % d == 0:
return False
return True
def is_prime_sqrt(n):
if n < 2: return False
if n % 2 == 0: return n == 2
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
n = 1000003
start = time.time()
res1 = is_prime_naive(n)
t1 = time.time() - start
start = time.time()
res2 = is_prime_sqrt(n)
t2 = time.time() - start
print(f"Наивный: {res1}, время {t1:.5f} сек")
print(f"Улучшенный: {res2}, время {t2:.5f} сек")Наивный: True, время 0.08323 сек Улучшенный: True, время 0.00009 сек
2. Генерация списка простых чисел до 10^6 с помощью решета Эратосфена
def sieve_all(n):
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, p in enumerate(is_prime) if p]
primes = sieve_all(1000000)
print(f"Количество простых до 1 млн: {len(primes)}")
print("Последние 5:", primes[-5:])Количество простых до 1 млн: 78498 Последние 5: [999961, 999979, 999983, 999997, 1000003]
3. Проверка простоты числа с помощью sympy (большое число)
from sympy import isprime
# Число 2^127 - 1 (простое Мерсенна)
n = 2**127 - 1
print("Длина числа:", len(str(n)), "цифр")
print("Простое?", isprime(n))Длина числа: 39 цифр Простое? True
4. Сегментированное решето для диапазона 10^12..10^12+1000
def sieve_eratosthenes(n):
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, p in enumerate(is_prime) if p]
def segmented_sieve(l, r):
if l < 2: l = 2
limit = int(r ** 0.5) + 1
small_primes = sieve_eratosthenes(limit)
is_prime_seg = [True] * (r - l + 1)
for p in small_primes:
start = max(p * p, ((l + p - 1) // p) * p)
for j in range(start, r + 1, p):
is_prime_seg[j - l] = False
return [i + l for i, v in enumerate(is_prime_seg) if v]
l = 10**12
r = l + 1000
primes_seg = segmented_sieve(l, r)
print(f"Простые числа в [{l}, {r}]:")
print(primes_seg)Простые числа в [1000000000000, 1000000001000]: [1000000000003, 1000000000033, 1000000000061, 1000000000063, 1000000000091, 1000000000093]
5. Тест Миллера-Рабина с детерминированными свидетелями для чисел до 2^64
def miller_rabin_deterministic(n):
# Для чисел < 2^64 достаточно проверить следующие a
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:
s += 1
d //= 2
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
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
# Тестируем на числах 2^61-1 (простое) и 2^61+1 (составное)
n1 = 2**61 - 1
n2 = 2**61 + 1
print(f"{n1}: {miller_rabin_deterministic(n1)}")
print(f"{n2}: {miller_rabin_deterministic(n2)}")2305843009213693951: True 2305843009213693953: False
6. Параллельный поиск простых чисел с помощью multiprocessing
from multiprocessing import Pool
import math
def is_prime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2
limit = int(math.isqrt(n))
for d in range(3, limit + 1, 2):
if n % d == 0:
return False
return True
def find_primes_parallel(limit, num_workers=4):
numbers = range(2, limit + 1)
with Pool(num_workers) as pool:
results = pool.map(is_prime, numbers)
return [n for n, prime in zip(numbers, results) if prime]
primes = find_primes_parallel(100000, 4)
print(f"Найдено {len(primes)} простых до 100000")
print("Первые 10:", primes[:10])Найдено 9592 простых до 100000 Первые 10: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]