Простые числа в Python

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

1. Проверка делителей:

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

В этом примере мы проверяем все числа от 2 до корня из n, и если n делится на любое из них, то оно не является простым числом. Этот подход имеет временную сложность O(√n).

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

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

Этот подход основан на алгоритме решета Эратосфена. Он помечает все числа, которые являются составными (не простыми), начиная с 2 и до квадратного корня из n. Затем все оставшиеся неотмеченными числа являются простыми. Возвращаем список простых чисел до n.

3. Рекурсивная проверка:

def is_prime_recursive(n, d=2):
    if n <= 1:
        return False
    if d == n:
        return True
    if n % d == 0:
        return False
    return is_prime_recursive(n, d+1)

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

Теперь вы можете использовать эти функции для проверки простых чисел в Python. Примеры вызова этих функций:

print(is_prime(17))  # True
print(is_prime(25))  # False

print(sieve_of_eratosthenes(30))  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

print(is_prime_recursive(37))  # True
print(is_prime_recursive(42))  # False

Все эти методы позволяют вам определить, является ли число простым на языке Python. Выбор метода зависит от вашего предпочтения и требований проекта. Хорошей практикой является использование функций из библиотеки math для более эффективных вычислений со временной сложностью O(√n).