Euler's totient function, also known as phifunction n, counts the number of integers between 1 and n inclusive, which are coprime to n. Two numbers are coprime if their greatest common divisor GCD equals 1. Euler's totient function or Phi function. Time Complexity: Osqrtn. result  n for i in range2, intn  0.5  1: if n  i  0: while n  i  0: n  i result  result  i if n  1: result  result  n return result
def euler_totient(n):
    """Euler's totient function or Phi function.
    Time Complexity: O(sqrt(n))."""
    result = n
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            while n % i == 0:
                n //= i
            result -= result // i
    if n > 1:
        result -= result // n
    return result
