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));
}