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

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

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

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 также прервется в том случае, если i2 (на языке Python возведение в степень обозначается **) станет больше n.

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

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

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

Или так:

divider(136)

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

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

num = 149
divider(num)

Блок-схема

Блок-схема к алгоритму `Перебор делителей`

Код должен документировать

Код должен документировать себя. Вместо комментария #флаг нужно дать переменной осмысленное имя и использовать булевы литералы. found = False или running = True

def divider(n): for i in

def divider(n):
    for i in range(2,int(n**0.5)):
        if n%i==0: 
            print("Это составное число")
            return
    else: 
        print("Это простое число")

замечательный пример

замечательный пример использования else к for

def isprime(x):
    for div in [i for i in xrange(2, x) if i**2 <= x]:
        if x % div == 0:
            print x, ' = ', div, " * ", x / div
            return
    else:
        print x, ' is a prime'