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 euler s totient function or phi function time complexity o sqrt n
def euler_totient(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