- студенты и школьники, изучающие Python и программирование
- люди, изучающие программирование на уроках или в кружках, связанных с разработкой и алгоритмами
- все, кто интересуется математическими алгоритмами и их реализацией на практике
Наивный метод
Простейший способ проверки — перебор всех чисел до корня из исследуемого числа.
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
Временная сложность: O(√n)
Пространственная сложность: O(1)
Подходит для небольших чисел и учебных целей
Улучшенный наивный метод
Мы можем оптимизировать перебор:
- Проверяем, делится ли число на 2.
- Если не делится, то перебираем только нечётные делители.
def is_prime(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
return True
Преимущества: Примерно в 2 раза быстрее наивного метода за счёт пропуска чётных чисел
Тест Ферма
Тест Ферма основан на малой теореме Ферма. Этот метод не дает гарантированного ответа, но позволяет с высокой вероятностью определить простоту числа. k=5 в алгоритме — это количество итераций теста Ферма, чем больше это число, тем больше вероятность, что число действительно простое.
import random
def fermat_test(n, k=5):
if n <= 1:
return False
for _ in range(k):
a = random.randint(1, n-1)
if pow(a, n-1, n) != 1:
return False
return True
Важно: Тест Ферма является вероятностным — он может ошибочно классифицировать некоторые составные числа как простые (числа Кармайкла).
Тест Миллера-Рабина
Это вероятностный тест, который позволяет с высокой точностью определить простоту числа, особенно для больших чисел.
k=5 в алгоритме — это количество итераций теста Миллера-Рабина, чем больше это число, тем больше вероятность, что число действительно простое.
import random
def miller_rabin_test(n, k=5):
if n <= 1:
return False
if n <= 3:
return True
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for _ in range(k):
a = random.randint(2, n - 1)
x = pow(a, s, 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
Есть множество методов проверки простоты числа. Выбор метода зависит от конкретной задачи. Для больших чисел рекомендуется использовать вероятностные тесты, такие как Ферма или Миллера-Рабина.
С помощью приведенных выше методов можно эффективно определить, является ли данное число простым, используя Python.