Практическая работа № 38
«Рекурсия»

Уровень A. Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида.

Пример:

Введите два натуральных числа:
7006652  112307574
НОД(7006652,112307574) = 1234.

Уровень B. Напишите рекурсивную функцию, которая раскладывает число на простые сомножители.

Пример:

Введите натуральное число:
378
378 = 2*3*3*3*7

Уровень C. Дано натуральное число N. Требуется получить и вывести на экран количество всех возможных различных способов представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной функции.

Пример:

Введите натуральное число:
4
Количество разложений: 4