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

[Антон]

Привет всем! Вот такой вопрос: как проверить просто ли число в питоне? Недавно начал разбираться с числами, и некоторым образом застрял на проверке простоты числа. Было бы круто, если бы кто-нибудь мог поделиться своим кодом или объяснить, как это сделать, желательно с примерами. Заранее спасибо!

[admin]

Ждём вас в нашем чате в Телеграмм ==>> @pythoneer_chat

А ТАКЖЕ: Канал о Python, статьи и книги ==>> @pythoneer_ru

[Анжела]

Короче, для проверки простоты числа можно использовать алгоритм пробного деления. Сначала проверяешь, что число больше 1, потом делишь на все числа до его квадратного корня. Если есть делитель больше 1 и меньше самого числа - оно не простое. Пример кода:

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

[Lancelot]

Короче, для проверки простоты числа можно использовать алгоритм пробного деления. Сначала проверяешь, что число больше 1, потом делишь на все числа до его квадратного корня. Если есть делитель больше 1 и меньше самого числа - оно не простое. Пример кода:

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

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

[StarRogue]

Есть более быстрые алгоритмы, например, решето Эратосфена для генерации всех простых чисел до большего числа. Можно использовать его, чтобы просеять и найти простые. Вот пример:

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

[Эльмира]

Есть более быстрые алгоритмы, например, решето Эратосфена для генерации всех простых чисел до большего числа. Можно использовать его, чтобы просеять и найти простые. Вот пример:

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

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

[WaterNymph]

Если особо заморачиваться не хочется, то можно просто использовать библиотеку sympy:

from sympy import isprime
print(isprime(17)) # True
print(isprime(20)) # False 

Она мощная и проверяет простоту чисел очень быстро.

[ГелиодоровыйЗакат]

Если особо заморачиваться не хочется, то можно просто использовать библиотеку sympy:

from sympy import isprime
print(isprime(17)) # True
print(isprime(20)) # False 

Она мощная и проверяет простоту чисел очень быстро.

Sympy рулит, да. Особенно когда нужно что-то быстро и легко на питоне сделать, вместо того чтобы городить свои функции.

[КаинитовыйРассвет]

Знаешь, если тебе нужно просто проверить простоту одного числа, чисто для себя, то можно юзать любой из предложенных вариантов. А вообще, пробное деление или решето Эратосфена для больших задач можно комбинировать. Например, сначала генерация решетом, а потом проверка образовавшимися числами.

[Нелля]

Знаешь, если тебе нужно просто проверить простоту одного числа, чисто для себя, то можно юзать любой из предложенных вариантов. А вообще, пробное деление или решето Эратосфена для больших задач можно комбинировать. Например, сначала генерация решетом, а потом проверка образовавшимися числами.

Типа гибридный метод? Не плохая идея! Инженерное решение так сказать: и просто, и быстро.