69
правок
Изменения
→Алгоритм
== Алгоритм ==
Используя доказанные выше свойства функции, получим алгоритм нахождения <math>\varphi(n)</math> через факторизацию числа, работающий за <math>O(\sqrt{n})</math>.
'''function''' phi (n):
result = n
i = 2
'''while''' (i*i <= n):
'''if''' n % i == 0:
'''while''' n % i == 0:
n /= i
result -= result / i
i++
'''if''' (n > 1):
result -= result/n
'''return''' result
== См. также ==
