Определение простых чисел в Python

• 14.01.2024
• 192
• Основы Python
• Числа

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

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

Простое число - это натуральное число, большее единицы, которое не имеет положительных делителей, кроме 1 и самого себя. Например, числа 2, 3, 5, 7, 11 и 13 являются простыми.

Методы проверки на простое число

Простой метод

Простой метод проверки на простоту заключается в проверке, делится ли число на любое число от 2 до числа, предшествующего ему.

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

Улучшенный метод

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

import math

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

Примеры использования

Продемонстрируем работу обоих методов на примерах.

import math

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

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

numbers = [1, 2, 3, 4, 5, 17, 19, 20]

print("Простой метод:")
for num in numbers:
    print(f"{num} простое число? {is_prime_naive(num)}")

print("\nУлучшенный метод:")
for num in numbers:
    print(f"{num} простое число? {is_prime_improved(num)}")
    
# Простой метод:
# 1 простое число? False
# 2 простое число? True
# 3 простое число? True
# 4 простое число? False
# 5 простое число? True
# 17 простое число? True
# 19 простое число? True
# 20 простое число? False
# 
# Улучшенный метод:
# 1 простое число? False
# 2 простое число? True
# 3 простое число? True
# 4 простое число? False
# 5 простое число? True
# 17 простое число? True
# 19 простое число? True
# 20 простое число? False

Заключение

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