Проверка простого числа

Простое число — это натуральное число больше 1, у которого нет других делителей, кроме 1 и самого себя. Например, 2, 3, 5, 7 — простые числа, а 6 — составное, потому что 2 × 3 = 6.

В этой статье разберём два способа проверить, простое ли число: с помощью переменной-флага и с помощью конструкции for...else.

Что нужно знать

Перед изучением примера полезно понимать:

Оператор if…else в Python — условный оператор if...else
Python: цикл for — цикл for
Python: break и continue — операторы break и continue

Пример 1. С переменной-флагом

# Program to check if a number is prime or not

num = 29

# To take input from the user
#num = int(input("Enter a number: "))

# define a flag variable
flag = False

if num == 0 or num == 1:
    print(num, "is not a prime number")
elif num > 1:
    # check for factors
    for i in range(2, num):
        if (num % i) == 0:
            # if factor is found, set flag to True
            flag = True
            # break out of loop
            break

    # check if flag is True
    if flag:
        print(num, "is not a prime number")
    else:
        print(num, "is a prime number")

Вывод

29 is a prime number

В программе проверяется, простое ли num. Числа, меньшие или равные 1, простыми не считаются — поэтому мы продолжаем только если num > 1.

Далее перебираются все целые делители от 2 до num - 1. Если найден хотя бы один делитель, число составное: устанавливаем флаг в True и выходим из цикла через break.

После цикла проверяем значение флага:

если он True — число не простое;
если False — простое.

Совет

Программу можно ускорить, сократив диапазон поиска делителей. Вместо range(2, num) используйте range(2, num//2) или range(2, math.floor(math.sqrt(num)+1)) — у составного числа обязательно есть делитель, не превосходящий корня из этого числа.

В Python ту же задачу можно решить и без флага — с помощью конструкции for...else.

Пример 2. Через конструкцию for…else

num = 407

# To take input from the user
#num = int(input("Enter a number: "))

if num == 0 or num == 1:
    print(num, "is not a prime number")
elif num > 1:
   # check for factors
   for i in range(2,num):
       if (num % i) == 0:
           print(num,"is not a prime number")
           print(i,"times",num//i,"is",num)
           break
   else:
       print(num,"is a prime number")

# if input number is less than
# or equal to 1, it is not prime
else:
   print(num,"is not a prime number")

Вывод

407 is not a prime number
11 times 37 is 407

Здесь применяется конструкция for...else: блок else цикла for выполняется только в том случае, если из цикла не выходили через break. То есть если не нашлось ни одного делителя, число объявляется простым. Очень удобный и идиоматичный для Python способ.