== Алгоритм ==
Используя доказанные выше свойства функции, получим алгоритм нахождения Основной идеей алгоритма является формула <mathtex>\displaystyle \varphi(n) = n\prod_{i = 1}^{r}(1 - \frac{1}{p_i})</tex>. Фактически для решения задачи нам нужны только простые делители числа <math> через n</math>. Их можно найти с помощью алгоритма факторизации. Написанный ниже алгоритм использует факторизацию числа, работающий работающую за <math>O(\sqrt{n})</math>, однако есть более [https://e-maxx.ru/algo/factorization эффективные алгоритмы]. Асимптотика вычисления <tex> \displaystyle \varphi(n)</tex> {{---}} <math>O(\sqrt{n})</math>.
'''function''' phi (n):
