Проверка числа на простоту с использованием рекурсии

Описание задачи

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

Решение задачи

  1. Принимаем число и записываем его в отдельную переменную.
  2. Передаем это число в качестве аргумента в рекурсивную функцию. В качестве второго аргумента этой рекурсивной функции будет переменная-делитель. Она при первом вызове инициируется значением None.
  3. Затем делителю присваивается значение на единицу меньшее, чем наше число, и проверяется, делится ли число на него без остатка. Если делится, программа завершает работу и определяет, что число не является простым.
  4. Если нет, то функция рекурсивно вызывает саму себя, причем второй аргумент (делитель) теперь на 1 меньше, чем был до этого.
  5. Таким образом, мы проверяем делимость исходного числа на все числа, которые меньше него и больше 1. Если хоть на одно из этих чисел оно делится без остатка, функция возвращает False. В противном случае число считается простым.
  6. Выводим результат на экран.
  7. Конец.

Исходный код

Ниже дан исходный код, который осуществляет проверку числа на простоту с использованием рекурсии. Результаты работы программы также даны ниже.

def check(n, div = None):
    if div is None:
        div = n - 1
    while div >= 2:
        if n % div == 0:
            print("Число не является простым")
            return False
        else:
            return check(n, div-1)
    else:
        print("Число является простым")
        return True
n = int(input("Введите число: "))
check(n)

Объяснение работы программы

  1. Принимаем число и записываем его в отдельную переменную n.
  2. Передаем это число в качестве аргумента в рекурсивную функцию check(). В качестве второго аргумента этой рекурсивной функции передается переменная div, которая будет делителем. Она при первом вызове инициируется значением None.
  3. Затем делителю присваивается значение на единицу меньшее, чем наше число, и проверяется, делится ли число на этот делитель без остатка. Если делится, программа завершает работу и определяет, что число не является простым.
  4. Если нет, то функция рекурсивно вызывает саму себя следующим образом: check(n, div-1). Заметьте, что второй аргумент div теперь на 1 меньше, чем был до этого.
  5. Таким образом мы проверяем делимость исходного числа на все числа, которые меньше него и больше 1. Если хоть на одно из этих чисел оно делится без остатка, функция возвращает False: число не является простым. А если нет, то число простое.
  6. Выводим результат на экран.

Результаты работы программы

Пример 1:
Введите число: 13
Число является простым
 
Пример 2:
Введите число: 30
Число не является простым

Примечание переводчика

Данный код приведен лишь для примера использования рекурсии. С вычислительной точки зрения он является крайне несовершенным. Так, например, рассматриваемый нами ранее алгоритм решета Эратосфена гораздо экономичней. В данном же коде есть недостатки. Например, совсем необязательно проверять, делится ли число n на n - 1 без остатка, и так ясно, что нет. Предоставим читателям возможность самим улучшить данный код.