Наивный метод
Простейший способ проверки — перебор всех чисел до корня из исследуемого числа.
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
Улучшенный наивный метод
Мы можем оптимизировать перебор:
-
Проверяем, делится ли число на 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
Получи больше пользы от Skysmart:
-
Научись программировать на курсах разработки.
-
Выбирай из 130+ наставников по программированию.
Записывайся на бесплатные курсы для детей.
Тест Ферма
Тест Ферма основан на малой теореме Ферма. Этот метод не дает гарантированного ответа, но позволяет с высокой вероятностью определить простоту числа. 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.
