Изменения

Перейти к: навигация, поиск

Обсуждение участника:MetaMockery

21 байт убрано, 11:10, 29 декабря 2020
Алгоритм
== Алгоритм ==
Основной идеей алгоритма является формула <tex> \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 эффективные алгоритмы].
Асимптотика вычисления <math> \displaystyle \varphi(n) = O(\sqrt{n})</math>.
Анонимный участник

Навигация