Прошу продемонстрировать рекурсивный алгоритм нахождения функции Эйлера(желательно на C/C++, но можно и на псевдокоде)?

Question

[misantropisk]

Прошу продемонстрировать рекурсивный алгоритм нахождения функции Эйлера(желательно на C/C++, но можно и на псевдокоде)?

Answer 1

[Армянское Радио]

Функцию НОД - алгоритм Евклида - напишите самостоятельно

typedef long long int enatural;
enatural _euler(enatural n,enatural k)
//шаг рекурсии. n - счетчик по всем числам от 1 до k и условие остановки рекурсии
//k - число, для которого вычисляем функцию Эйлера
{
   //функция Эйлера от 1 равна 1
   if(n==1)
   {
       return(1);
   }
   //функция Эйлера в рекурсивном варианте - если n взаимно просто с k, то она равна 1+(функция Эйлера от n-1)
   if(nod(n,k)==1) //если число взаимно просто, увеличиваем количество
   {
       return(1+_euler(n-1,k));
   }
   //в противном случае она просто равна функции Эйлера от n-1
   return(_euler(n-1,k));
}
enatural euler(enatural n)
{
    return(_euler(n,n));
}

Comments

[misantropisk]

Arigato

[misantropisk]

Армянское Радио а что означает _euler(n-1, k), почему мы число само уменьшаем на 1, и что такое параметр k?

[Eddy_Em]

Во-первых, рекурсия — плохо. Задаем достаточно большое число и переполняем стек.
Во-вторых, эти элементарные функции уже давным-давно есть во всех уважающих себя математических библиотеках. Зачем ТСу нужно велосипедостроением заниматься, мне непонятно. Ну, а если хочется стырить чужой код, достаточно было бы посмотреть "C snippets".

[Армянское Радио]

Японский Городовой: Ну попросили рекурсию, я влепил рекурсию. Математики функцию Эйлера так и вовсе без рекурсии считают, а используют факторизацию.
В учебных целях посмотреть на хороший код иногда бывает полезно.

misantropisk: посмотрите ответ, я добавил пояснения