def euler_totient(n):
result = n;<EOL>for i in range(<NUM_LIT:2>, int(n ** <NUM_LIT:0.5>) + <NUM_LIT:1>):<EOL><INDENT>if n % i == <NUM_LIT:0>:<EOL><INDENT>while n % i == <NUM_LIT:0>:<EOL><INDENT>n //= i<EOL><DEDENT>result -= result // i<EOL><DEDENT><DEDENT>if n > <NUM_LIT:1>:<EOL><INDENT>result -= result // n;<EOL><DEDENT>return result<EOL>
Euler's totient function or Phi function.
    Time Complexity: O(sqrt(n)).