Реализация проверки на простое число в Python
Наиболее эффективный детерминированный алгоритм проверки простоты
Для чисел, не превышающих 2^64, можно использовать оптимизированный перебор делителей. Алгоритм основан на проверке только до квадратного корня из числа, с дополнительным исключением делителей, кратных 2 и 3. Это дает высокую скорость для большинства практических задач.
def is_prime(n):
if n < 2:
return False
if n in (2, 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
алгоритм задачи python (алгоритмы задач на python)
Пояснение: после проверки на четность и кратность 3, перебираются числа вида 6k±1 (начиная с 5). Шаг 6 позволяет не проверять числа, которые делятся на 2 или 3, что сокращает количество итераций примерно в 3 раза по сравнению с проверкой всех чисел до корня.
Типичные ошибки и проблемы:
- Не учтены числа меньше 2: возвращать False.
- Использование цикла до n вместо sqrt(n) приводит к крайне медленной работе для больших чисел.
- Для вещественных чисел или чисел с плавающей точкой алгоритм не предназначен. Необходимо передавать целые числа.
Как сделать проверку с помощью наивного перебора?
Самый простой, но медленный способ: проверять все числа от 2 до n-1. Если хотя бы одно делит n без остатка, то n составное. Подходит только для очень маленьких чисел (до нескольких тысяч).
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=10^9 потребуется огромное количество операций. Также неэффективен для повторных проверок.
Как улучшить наивный метод, проверяя только до квадратного корня?
Достаточно проверить делители до sqrt(n), так как если n = a*b, то один из множителей не превышает sqrt(n).
import math
def is_prime_sqrt(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, int(math.isqrt(n)) + 1, 2):
if n % i == 0:
return False
return TruePython алгоритмы языка (алгоритмы в python)
Проблема: даже до sqrt(n) для чисел порядка 10^12 требуется около 500 000 итераций, что приемлемо, но для 10^18 уже 500 млн, что медленно. Требуется дальнейшая оптимизация.
Как использовать решето Эратосфена для проверки одного числа?
Решето Эратосфена эффективно для нахождения всех простых чисел до некоторой границы. Если нужно проверить только одно число, можно предварительно построить решето до sqrt(n) и затем проверить делимость на простые из решета.
def sieve_primes(limit):
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, int(limit**0.5) + 1):
if is_prime[p]:
for multiple in range(p*p, limit+1, p):
is_prime[multiple] = False
return [i for i, prime in enumerate(is_prime) if prime]
def is_prime_sieve(n):
if n < 2:
return False
limit = int(math.isqrt(n))
primes = sieve_primes(limit)
for p in primes:
if n % p == 0:
return False
return Trueалгоритмы с примерами на python (примеры алгоритмов на python)
Проблема: требует построения решета до sqrt(n), что занимает O(sqrt(n) log log sqrt(n)) времени и O(sqrt(n)) памяти. Для больших n это может быть неэффективно.
Как применить вероятностный тест Ферма?
Малая теорема Ферма: если n простое, то для любого a (1 < a < n) выполняется a^(n-1) ≡ 1 (mod n). Если это не выполняется, n составное. Однако существуют числа Кармайкла, которые проходят тест для многих a.
def fermat_test(n, k=5):
if n < 2:
return False
if n in (2, 3):
return True
import random
for _ in range(k):
a = random.randint(2, n-2)
if pow(a, n-1, n) != 1:
return False # составное
return True # вероятно простоеПроблемы: числа Кармайкла (например, 561) могут быть ошибочно признаны простыми. Тест только вероятностный, не детерминированный.
Как получить достоверную проверку с помощью теста Миллера-Рабина?
Тест Миллера-Рабина - улучшенный вероятностный тест, не подверженный числам Кармайкла. Для 32-битных чисел можно выбрать детерминированный набор свидетелей.
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 = d * 2^s
s = 0
d = n - 1
while d % 2 == 0:
d //= 2
s += 1
import random
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 # вероятно простоеПроблемы: сложнее в реализации, требуется правильное разложение n-1. Для абсолютной достоверности нужно выполнить тест с достаточным числом итераций. При k=10 вероятность ошибки менее 1/2^20.
Дополнительные примеры и их результаты
Проверка различных чисел с помощью оптимизированного алгоритма
Применим функцию is_prime (алгоритм 6k±1) для набора чисел, включая большие простые и составные.
def is_prime(n):
if n < 2:
return False
if n in (2, 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
numbers = [1, 2, 3, 4, 17, 1000000007, 999999999989, 1000000008]
for num in numbers:
print(f'{num}: {is_prime(num)}')1: False 2: True 3: True 4: False 17: True 1000000007: True 999999999989: True 1000000008: False
Детерминированный тест Миллера-Рабина для 32-битных чисел
Для чисел меньше 2^32 можно использовать фиксированный набор свидетелей [2, 7, 61] или [2,3,5,7,11] для 64-битных. Реализуем детерминированную версию.
def miller_rabin_deterministic(n):
if n < 2:
return False
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
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
# Проверка известных простых и чисел Кармайкла
for val in [2, 3, 17, 561, 1105, 1000000007, 999999999989]:
print(f'{val}: {miller_rabin_deterministic(val)}')2: True 3: True 17: True 561: False 1105: False 1000000007: True 999999999989: True
Использование библиотеки sympy для проверки простоты
Библиотека sympy предоставляет функцию isprime, реализующую комбинацию тестов (включая Миллера-Рабина). Установка: pip install sympy.
from sympy import isprime
for n in [1, 2, 17, 561, 10**9+7]:
print(f'{n}: {isprime(n)}')1: False 2: True 17: True 561: False 1000000007: True
Сравнение производительности алгоритмов на большом числе
Измерим время выполнения наивного, sqrt-оптимизированного и 6k±1 алгоритмов для числа 1000000007 с помощью timeit.
import timeit
def naive(n):
for i in range(2, n):
if n % i == 0:
return False
return True
def sqrt_opt(n):
if n < 2:
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
return True
def sixk_opt(n):
if n < 2:
return False
if n in (2,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
n = 1000000007
print('Naive:', timeit.timeit(lambda: naive(n), number=1))
print('Sqrt opt:', timeit.timeit(lambda: sqrt_opt(n), number=10))
print('6k±1 opt:', timeit.timeit(lambda: sixk_opt(n), number=10))Naive: (занимает очень много времени, не стали запускать) Sqrt opt: 0.00015 сек за 10 запусков 6k±1 opt: 0.00009 сек за 10 запусков
Примечание: Наивный метод не запускался из-за огромного времени выполнения. Оптимизации дают значительное ускорение.