Быстрое вычисление функции Эйлера
Primary tabs
Есть вот такой вот изящный алгоритм, использующий метод факторизации:
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
реализация на пхп доступна здесь = http://fkn.ktu10.com/?q=node/4249
- vedro-compota's blog
- Log in to post comments
- 9147 reads