Научим создавать свои игры, сайты и приложения
Начать учиться

Проверка на простое число в Python

Проверка на простое число в Python
21.8K

Проверка на простое число часто встречается в задачах по математике и программировании. Простое число — это число, которое делится только на 1 и на себя. В этой статье мы рассмотрим несколько методов проверки на простое число с использованием 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

Улучшенный наивный метод

Мы можем оптимизировать перебор:

  1. Проверяем, делится ли число на 2.

  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:

Тест Ферма

Тест Ферма основан на малой теореме Ферма. Этот метод не дает гарантированного ответа, но позволяет с высокой вероятностью определить простоту числа. 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.

Комментарии

Открыть диалоговое окно с формой по клику
Бесплатный вебинар
Бесплатный вебинар
Бесплатный вебинар
Научиться разработке
Подготовиться к ОГЭ/ЕГЭ
Получите план развития в программировании
  • Поможем с выбором IT-профессии
  • Вместе сделаем первый проект
  • Расскажем, как проходят занятия
Шаг 1 из 2
Шаг 1 из 2
Шаг 2 из 2