адача 24. Составить рекурсивную программу-функцию проверяющую, является ли заданное натуральное число n простым?

Решение. Пусть рекурсивная функция isprim(n) является решением задачи и

Дальнейшие рассуждения являются иллюстрацией использования классического приема “Обобщить” (см. схему 3 решения задач с помощью рекурсии). Перейдем к рассмотрению следующей обобщенной задачи.

Пусть a, b, n - натуральные числа и 2£a£b£n. Верно ли, что заданное n не делится ни на одно целое из отрезка [a,b]?

Обозначим функцию решения этой задачи через nodiv():

Ниже приведено три рекурсивных варианта реализации данной функции. По первому из них проверке на делитель n последовательно подвергаются числа a, a+1, … , b; по второму - эти же числа в обратном порядке, и, наконец, по третьему движение к рекурсивной базе осуществляется сразу с двух сторон - a, b, a+1, b-1, … :

Далее, натуральное число n³2 является простым, если оно не имеет делителей на отрезке , поэтому характеристическая функция isprim(n) через функцию nodiv(n,a,b) может быть выражена так:

адача 25. Составить рекурсивную программу-функцию pi(x), которая подсчитывает количество простых чисел, не превосходящих заданное число x.

Решение. С помощью функций nodiv() или isprim() рекурсивный вариант функции pi(x) строится достаточно просто, исходя из такого декомпозиционного утверждения. Количество простых чисел, не превосходящих x, составляется из количества простых чисел, меньших или равных x-1, плюс значение функции isprim(x). Поэтому:

Контрольные примеры:

адача 26. Составить программу pn(n), которая вычисляет n-е простое число (n - натуральное).

Решение. Предварительно напишем рекурсивную подпрограмму-функцию minp(m) нахождения наименьшего простого числа, большего или равного m (m – натуральное число). Сделать это можно, например, так:

Контрольные примеры:

Тогда искомая функция pn(n) может быть определена так:

Контрольные примеры.