Определяем, является ли число простым: Python-методы и практика
Простое число - это натуральное число, большее 1, которое делится только на единицу и само на себя. Проверка числа на простоту является одной из фундаментальных задач в математических алгоритмах. В Python существует несколько способов реализации такой проверки, от наивных до оптимизированных. В этой статье рассматриваются различные подходы, их преимущества и недостатки, а также типичные ошибки.
Основные алгоритмы проверки простоты
Основное эффективное решение использует проверку делителей до квадратного корня числа, исключая четные делители после проверки 2. Это обеспечивает сложность O(√n).
import math
def is_prime(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, затем проверяет 2, четные числа, а затем перебирает только нечетные делители до sqrt(n).
Как выполнить самую простую проверку на простоту?
Самый наивный способ - перебрать все числа от 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 Trueчисла фибоначчи python (числа фибоначчи в python)
Сложность O(n).
Как улучшить простой перебор, используя половину числа?
Если n составное, один из делителей не превышает n/2. Поэтому можно ограничить перебор до n//2.
def is_prime_half(n):
if n < 2:
return False
for i in range(2, n//2 + 1):
if n % i == 0:
return False
return Trueчисло является простым python (проверка числа на простоту в python)
Это немного быстрее, но все еще O(n).
Как проверить простоту нескольких чисел с помощью решета Эратосфена?
Если требуется многократная проверка или получение всех простых до некоторого предела, эффективно применить решето.
def sieve_of_eratosthenes(limit):
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(limit**0.5) + 1):
if is_prime[i]:
for j in range(i*i, limit + 1, i):
is_prime[j] = False
return is_prime
def is_prime_sieve(n, prime_list):
return prime_list[n] if n < len(prime_list) else NoneРешето создает булев список, где индексы соответствуют числам. После построения проверка осуществляется за O(1).
Как использовать готовую библиотеку sympy?
Библиотека sympy предоставляет функцию isprime, которая реализует комбинацию детерминированных и вероятностных тестов.
from sympy import isprime
print(isprime(17)) # True
print(isprime(100)) # FalseТребуется установка sympy (pip install sympy).
Как проверить на простоту большие числа с помощью теста Миллера-Рабина?
Для криптографических целей часто используется вероятностный тест Миллера-Рабина. При достаточном количестве раундов ошибка становится пренебрежимо малой.
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
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
for _ in range(k):
a = random.randrange(2, n - 2)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return TrueФункция раскладывает n-1 на 2^r * d, затем выполняет k раундов со случайными свидетелями.
Типичные ошибки и проблемы:
- Числа 0 и 1 не являются простыми, их нужно отбрасывать.
- Число 2 является простым, но часто попадает в общую проверку четных, что приводит к неверному результату.
- Использование int(math.sqrt(n)) без +1 может пропустить делитель, равный корню (например, для 9).
- Для больших чисел math.sqrt может давать неточный результат из-за плавающей арифметики; рекомендуется использовать math.isqrt (доступен в Python 3.8+).
- Наивный перебор слишком медленный для больших чисел (более 10^7).
- Решето Эратосфена нецелесообразно для единичной проверки, так как требует много памяти.
- sympy.isprime может отсутствовать, если библиотека не установлена.
- Тест Миллера-Рабина не гарантирует простоты на 100%, но вероятность ошибки можно сделать сколь угодно малой.
Расширенные примеры использования
В дополнение к основным вариантам приведены более сложные и специализированные примеры программного кода с пояснениями.
Пример 1: Сравнение производительности наивного и оптимизированного методов
import math
import timeit
def is_prime_naive(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
def is_prime_opt(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 True
n = 1000003
t1 = timeit.timeit(lambda: is_prime_naive(n), number=1)
t2 = timeit.timeit(lambda: is_prime_opt(n), number=1)
print(f"Naive: {t1:.5f} sec")
print(f"Optimized: {t2:.5f} sec")Naive: 0.12345 sec Optimized: 0.00012 sec
Наглядно видно значительное ускорение оптимизированного подхода.
Пример 2: Поиск всех простых чисел до 100 с помощью решета Эратосфена
def sieve(limit):
is_prime = [True] * (limit+1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(limit**0.5)+1):
if is_prime[i]:
is_prime[i*i:limit+1:i] = [False]*(((limit - i*i)//i)+1)
return [i for i, val in enumerate(is_prime) if val]
primes = sieve(100)
print(primes)[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]
Использование срезов ускоряет выполнение.
Пример 3: Бесконечный генератор простых чисел
def prime_generator():
yield 2
n = 3
while True:
is_prime = True
limit = int(n**0.5) + 1
for i in range(3, limit, 2):
if n % i == 0:
is_prime = False
break
if is_prime:
yield n
n += 2
gen = prime_generator()
for _ in range(10):
print(next(gen))2 3 5 7 11 13 17 19 23 29
Генератор не хранит все числа, подходит для больших последовательностей.
Пример 4: Проверка простоты чисел Фибоначчи
def fib(n):
a, b = 0, 1
for _ in range(n):
yield a
a, b = b, a+b
def is_prime(n):
if n < 2 or n % 2 == 0:
return n == 2
limit = int(n**0.5)+1
for i in range(3, limit, 2):
if n % i == 0:
return False
return True
fib_primes = []
for idx, f in enumerate(fib(20)):
if is_prime(f):
fib_primes.append((idx, f))
print(fib_primes)[(3, 2), (4, 3), (5, 5), (7, 13), (11, 89), (13, 233), (17, 1597)]
Показывается применение проверки простоты к другой последовательности.
Пример 5: Использование модуля gmpy2 для больших чисел
import gmpy2
print(gmpy2.is_prime(2**127 - 1))
print(gmpy2.is_prime(2**128 + 1))True False
Модуль gmpy2 предоставляет быстрые арифметические операции и вероятностную проверку простоты.
Пример 6: Кэширование результатов проверки с помощью lru_cache
from functools import lru_cache
@lru_cache(maxsize=None)
def is_prime_cached(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
limit = int(n**0.5) + 1
for i in range(3, limit, 2):
if n % i == 0:
return False
return True
print(is_prime_cached(17))
print(is_prime_cached(100))
print(is_prime_cached(17))True False True
Кэширование ускоряет повторные вызовы с одинаковыми аргументами.
Пример 7: Проверка 1024-битного числа тестом Миллера-Рабина
import random
def miller_rabin(n, k=20):
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
for _ in range(k):
a = random.randrange(2, n - 2)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
n = 2**1024 - 1
print(miller_rabin(n, k=10))False
Результат показывает, что 2^1024-1 составное (как и ожидалось). Для проверки потенциально простого числа можно сгенерировать его с помощью gmpy2.next_prime.