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

36.3K

Проверка на простое число часто встречается в задачах по математике и программировании. Простое число — это число, которое делится только на 1 и на себя. В этой статье мы рассмотрим несколько методов проверки на простое число с использованием Python.

В Roblox можно больше, чем просто играть

Научим детей и подростков программировать и создавать миры в Roblox

Наивный метод

Простейший способ проверки — перебор всех чисел до корня из исследуемого числа.

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

185.1K

Какая профессия тебе подходит? Узнай за 10 минут!

Получи больше пользы от 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.