Найти в Дзене
Техника мебели ООО "ТМ"
1762 подписчика

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

1 мин
Простое число - это натуральное число, большее единицы, которое делится без остатка только на себя и на единицу. def is_prime(num):
"""Проверяет, является ли число простым.
Args:
num: Проверяемое число.
Returns:
True, если число простое, иначе False.
"""
# Частные случаи
if num <= 1:
return False
if num <= 3:
return True
# Все четные числа (кроме 2) составные
if num % 2 == 0:
return False
# Проверяем на делимость нечетными числами до корня из числа
i = 3
while i * i <= num:
if num % i == 0:
return False
i += 2
return True
# Пример использования
number = 17
if is_prime(number):
print(number, "является простым числом")
else:
print(number, "не является простым числом") Дополнительные оптимизации (для очень больших чисел):
Оглавление

Простое число - это натуральное число, большее единицы, которое делится без остатка только на себя и на единицу.

Алгоритм проверки

  1. Проверка на 1 и 2: Числа 1 и 2 являются частными случаями.
  2. Проверка на четность: Все четные числа (кроме 2) составные.
  3. Проверка на делимость нечетными числами до корня из числа: Если число делится без остатка на какое-либо нечетное число до своего корня, то оно составное.

Реализация на Python

def is_prime(num):
"""Проверяет, является ли число простым.

Args:
num: Проверяемое число.

Returns:
True, если число простое, иначе False.
"""

# Частные случаи
if num <= 1:
return False
if num <= 3:
return True
# Все четные числа (кроме 2) составные
if num % 2 == 0:
return False

# Проверяем на делимость нечетными числами до корня из числа
i = 3
while i * i <= num:
if num % i == 0:
return False
i += 2
return True

# Пример использования
number = 17
if is_prime(number):
print(number, "является простым числом")
else:
print(number, "не является простым числом")

Объяснение кода:

  • Функция is_prime(num): Принимает число num и возвращает True, если оно простое, иначе False.
  • Частные случаи: Отдельно обрабатываются числа 1, 2 и 3.
  • Проверка на четность: Если число четное и не равно 2, то оно сразу считается составным.
  • Цикл while: Проверяет делимость числа на нечетные числа от 3 до корня из числа. Если найдется делитель, то число составное.
  • Оптимизация: Цикл начинается с 3 и увеличивается на 2, чтобы проверять только нечетные числа.

Почему так?

  • Корень числа: Достаточно проверить делимость до корня из числа, так как если у числа есть делитель больший корня, то у него обязательно есть делитель меньший корня.
  • Нечетные числа: После проверки на четность достаточно проверять только нечетные числа.

Дополнительные оптимизации (для очень больших чисел):

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