Как проверить число на простоту с помощью Python? 🧮

Чтобы проверить число на простоту в Python, вы можете использовать следующую функцию:

def is_prime(number):
    if number < 2:
        return False
    for i in range(2, int(number ** 0.5) + 1):
        if number % i == 0:
            return False
    return True

# Пример вызова функции
number = 17
if is_prime(number):
    print(f"{number} является простым числом")
else:
    print(f"{number} не является простым числом")
    

Как проверить число на простоту в Python

Проверка числа на простоту в программировании - очень важная задача. Простое число - это число, которое делится нацело только на 1 и на само себя. В этой статье мы рассмотрим несколько способов проверки числа на простоту с помощью языка программирования Python.

Метод перебора делителей

Один из самых простых способов проверки числа на простоту - это перебор делителей от 2 до корня из числа. Если число делится нацело хотя бы на один из этих делителей, то оно не является простым. В противном случае, оно является простым.

import math

def is_prime(number):
    if number < 2:
        return False
    for divisor in range(2, int(math.sqrt(number)) + 1):
        if number % divisor == 0:
            return False
    return True

number = 17
if is_prime(number):
    print(f"{number} является простым числом")
else:
    print(f"{number} не является простым числом")

В приведенном выше коде, мы используем функцию is_prime для проверки числа на простоту. Если число меньше 2, то оно не является простым, поэтому мы возвращаем False. Затем мы перебираем делители от 2 до корня из числа, и если находим делитель, на которое число делится нацело, то оно не является простым, и мы возвращаем False. Если ни один делитель не найден, то число является простым, и мы возвращаем True.

В приведенном примере, число 17 является простым, поэтому будет выведено сообщение "17 является простым числом".

Метод решета Эратосфена

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

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

def is_prime(number):
    if number < 2:
        return False
    sieve = sieve_of_eratosthenes(number)
    return sieve[number]

number = 17
if is_prime(number):
    print(f"{number} является простым числом")
else:
    print(f"{number} не является простым числом")

В приведенном выше коде, мы используем функцию sieve_of_eratosthenes, чтобы сгенерировать решето Эратосфена для всех чисел до заданного числа. Затем мы используем функцию is_prime, чтобы проверить, является ли заданное число простым, используя сгенерированное решето. Если число является простым, мы возвращаем True, в противном случае - False.

В приведенном примере, число 17 является простым, поэтому будет выведено сообщение "17 является простым числом".

Метод теста простоты Миллера-Рабина

Еще один алгоритм для проверки числа на простоту - это тест простоты Миллера-Рабина. Этот алгоритм использует случайные числа и вероятностный подход для определения простоты числа.

import random

def miller_rabin_test(number, k=5):
    if number < 2:
        return False
    if number == 2 or number == 3:
        return True
    if number % 2 == 0:
        return False

    def check_a(a, s, d, number):
        x = pow(a, d, number)
        if x == 1 or x == number - 1:
            return True
        for _ in range(s - 1):
            x = pow(x, 2, number)
            if x == number - 1:
                return True
        return False

    s = 0
    d = number - 1
    while d % 2 == 0:
        s += 1
        d //= 2

    for _ in range(k):
        a = random.randint(2, number - 2)
        if not check_a(a, s, d, number):
            return False
    return True

number = 17
if miller_rabin_test(number):
    print(f"{number} является простым числом")
else:
    print(f"{number} не является простым числом")

В приведенном выше коде, мы используем функцию miller_rabin_test для проверки числа на простоту с помощью теста Миллера-Рабина. Если число является простым, мы возвращаем True, в противном случае - False.

В приведенном примере, число 17 является простым, поэтому будет выведено сообщение "17 является простым числом".

Заключение

В этой статье мы рассмотрели несколько способов проверки числа на простоту в Python. Вы можете использовать метод перебора делителей, решето Эратосфена или тест Миллера-Рабина, в зависимости от ваших конкретных потребностей.

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