🔎 Как сделать проверку на простое число в Питоне?

Чтобы проверить, является ли число простым в 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 = int(input("Введите число: "))
if is_prime(number):
    print("Число", number, "является простым.")
else:
    print("Число", number, "не является простым.")
    

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

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

1. Проверка делением на все числа до самого числа

Одним из наиболее простых и понятных методов является проверка делением на все числа до самого числа. Мы можем написать функцию, которая будет делить число на все числа от 2 до самого числа минус 1 и проверять остаток от деления. Если хотя бы для одного числа остаток равен 0, значит число не является простым.

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

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

2. Проверка делением на корень из числа

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

import math

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

В этом случае мы импортируем модуль math для использования функции sqrt(), которая возвращает квадратный корень числа n. Затем мы используем цикл со значениями от 2 до корня из n плюс 1 для проверки деления.

3. Решето Эратосфена

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

def sieve_of_eratosthenes(n):
    if n < 2:
        return []
    prime = [True] * (n + 1)
    prime[0] = prime[1] = False
    p = 2
    while p ** 2 <= n:
        if prime[p]:
            for i in range(p ** 2, n + 1, p):
                prime[i] = False
        p += 1
    primes = []
    for i in range(n + 1):
        if prime[i]:
            primes.append(i)
    return primes

def is_prime(n):
    return n in sieve_of_eratosthenes(n)
  

В этом примере мы сначала создаем список prime длиной n + 1 и заполняем его значениями True, предполагая, что все числа являются простыми. Затем мы устанавливаем значения prime[0] и prime[1] в False, так как 0 и 1 не являются простыми числами. Затем мы начинаем проходить по числам от 2 до квадратного корня из n, и если текущее число является простым (prime[p] равно True), мы помечаем все его кратные числа в списке prime как непростые. После завершения алгоритма все простые числа находятся в списке primes. Функция is_prime(n) возвращает True, если число n находится в этом списке, и False в противном случае.

Заключение

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