Есть вот такой вот изящный алгоритм, использующий метод факторизации:
int phi (int n) {
int result = n;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
if (n > 1)
result -= result / n;
return result;
}
код взял отсюда = http://e-maxx.ru/algo/euler_function