Как определить, является ли число простым?

Пользователь

от justice , в категории: Образование , 8 месяцев назад

Как определить, является ли число простым?

Facebook Vk Ok Twitter Telegram Whatsapp

1 ответ

Пользователь

от waldo , 8 месяцев назад

@justice 

Для определения, является ли число простым, можно применить следующий алгоритм:

  1. Проверить, является ли число меньше двух. Если это так, то число не является простым.
  2. Проверить, делится ли число нацело на какое-либо число от 2 до квадратного корня из числа. Если делится, то число не является простым.
  3. Если число не поделилось ни на одно число от 2 до квадратного корня из числа, то оно является простым.


Пример реализации этого алгоритма на языке Python:

1
2
3
4
5
6
7
8
9
import math

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


Теперь мы можем использовать эту функцию, чтобы определить, является ли число простым. Например:

1
2
3
print(is_prime(7))  # True
print(is_prime(10))  # False
print(is_prime(31))  # True