Тестирование простоты числа методом перебора делителей

Перебор делителей – это алгоритм, применяемый для определения, какое число перед нами: простое или составное.

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

def divider(n):
    i = 2
    j = 0 # флаг
    while i**2 <= n and j != 1:
        if n%i == 0:
            j = 1
        i += 1
    if j == 1:
        print ("Это составное число")
    else:
        print ("Это простое число")

При вызове этой функции на место параметра n подставляется число, которое надо протестировать на простоту.

Значения переменной i играют роль делителей. Первым значением делителя является 2, далее происходит увеличение за каждый оборот цикла while на единицу.

Выражение n % i возвращает остаток от деления первого числа на второе. Если остаток равен 0, т.е. первое число делится нацело на второе, то n является составным числом. В этом случае переменная, играющая роль флага (j) меняет свое значение, и цикл while больше не выполняется (из-за выражения j != 1).

Цикл while также прервется в том случае, если i² (на языке Python возведение в степень обозначается **) станет больше n.

Конструкция if – else просто выполняет анализ значения, с которым связана флаг-переменная, в зависимости от ее состояния выводит соответствующий текст на экран.

Вызвать функцию divider можно так:

divider(int(input("Введите число:")))

Или так:

divider(136)

В первом случае ввод пользователя преобразуется из строчного типа в целое число с помощью функции int. Полученное значение передается функции divider.

Если требуется хранить значение проверяемого числа, то его следует связать с переменной:

num = 149
divider(num)

Блок-схема