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

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

Что такое простое число?

Простое число — это натуральное число, большее 1, которое не имеет других делителей, кроме 1 и самого себя. Например:

• Простые числа: 2, 3, 5, 7, 11, 13…
• Составные числа: 4, 6, 8, 9, 10…

Способ 1: Простой перебор делителей

Наиболее очевидный способ проверки на простое число — это проверить, делится ли число на любое число от 2 до n-1 без остатка.

Код

def is_prime_basic(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

# Пример использования
print(is_prime_basic(7))  # True
print(is_prime_basic(10))  # False

Объяснение

• Функция принимает число n и проверяет все числа от 2 до n-1.
• Если для какого-либо числа выполняется условие n % i == 0, то число не является простым, и функция возвращает False.
• Если перебор всех чисел завершен и делителей не найдено, число считается простым, и функция возвращает True.

Минусы: Этот метод является неэффективным для больших чисел, поскольку проверяет слишком много делителей.

Способ 2: Оптимизация с использованием квадратного корня

Мы можем оптимизировать предыдущий алгоритм, проверяя делители только до квадратного корня числа. Это связано с тем, что если число n имеет делитель больше своего квадратного корня, то оно обязательно имеет меньший делитель.

Код

import math

def is_prime_optimized(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

# Пример использования
print(is_prime_optimized(7))  # True
print(is_prime_optimized(10))  # False

Объяснение

• Вместо проверки всех чисел до n, мы проверяем только до √n.
• Это существенно уменьшает количество проверок, что улучшает производительность для больших чисел.

Преимущества: В несколько раз быстрее, чем простой перебор.

Способ 3: Проверка только нечетных чисел

Кроме числа 2, все остальные простые числа нечетные. Таким образом, можно дополнительно оптимизировать алгоритм, проверяя делители только для нечетных чисел после проверки на делимость на 2.

Код

import math

def is_prime_efficient(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

# Пример использования
print(is_prime_efficient(11))  # True
print(is_prime_efficient(25))  # False

Объяснение

• Сначала мы проверяем число на делимость на 2.
• Если число нечетное, проверяем делимость только для нечетных чисел начиная с 3.

Преимущества: Еще меньшее количество проверок.

Способ 4: Решето Эратосфена

Этот метод подходит для поиска всех простых чисел до определенного предела. Он работает за счет последовательного исключения составных чисел, оставляя только простые числа.

Код

import math

def sieve_of_eratosthenes(limit):
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.sqrt(limit)) + 1):
        if sieve[i]:
            for j in range(i * i, limit + 1, i):
                sieve[j] = False
    return [i for i in range(limit + 1) if sieve[i]]

# Пример использования
print(sieve_of_eratosthenes(50))  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Объяснение

• Этот метод создает массив длиной limit + 1, где каждое число помечается как простое или составное.
• Начинаем с 2 и удаляем все кратные числа из массива. Оставшиеся числа будут простыми.

Преимущества: Подходит для поиска всех простых чисел в диапазоне. Особенно эффективен для больших диапазонов.

Способ 5: Использование встроенных библиотек

В Python существуют сторонние библиотеки для работы с простыми числами, например, библиотека sympy. Она содержит готовую функцию для проверки числа на простоту.

Чтобы установить библиотеку sympy, используйте команду pip, которая является стандартным инструментом для управления пакетами в Python.

Откройте терминал (или командную строку) и выполните следующую команду:

pip install sympy

Код

from sympy import isprime

# Пример использования
print(isprime(7))  # True
print(isprime(25))  # False

Объяснение

• Библиотека sympy предоставляет функцию isprime(), которая использует эффективные алгоритмы для проверки числа на простоту.

Преимущества: Простота использования и высокая эффективность.