Ad

The totient function of a number is defined as the number of numbers less than that number that do not share a factor with that number.

Define a function totient(a) that computes the totient of a number.

def totient(a):
    out = 0
    for b in range(a):
        if(gcd(a, b) == 1):
            out += 1
    return out
    
def gcd(a, b):
    while b != 0:
        (a, b) = (b, a % b)
    return a