Euler Totient Function

Euler Totient Function (denoted by $\phi$) of a number $n$ is the number of numbers which are co-prime to and less than $n$

# function to determine if a number is prime
def isPrime(n):
    if n == 2:
        return True
    k = n >> 1
    for i in range(2,k + 1):
        if not n % i:
            return False
    return True

def eulerTotient(n):
    if isPrime(n):
        return [i for i in range(1,n)]
    arr = [1]
    # 2 consecutive numbers are always co-prime that's why check till n-2
    for i in range(2,n-1):
        isValid = (n % i) != 0
        if isValid:
            j = 2
            k = i>>1
            while j <= k:
                isValid = (i % j) or (n % j)
                if not isValid:
                    break
                j += 1
            if isValid:
                arr.append(i)
    arr.append(n-1)
    return arr

Driver Code

if __name__=="__main__":
    num = [7, 8, 9, 10, 11]
    for n in num:
        arr = eulerTotient(n)
        print(f'\nPHI({n}) = {len(arr)}')
        for i in arr:
            print(i,end=' ')
        print()

PHI(7) = 6
1 2 3 4 5 6 

PHI(8) = 4
1 3 5 7 

PHI(9) = 6
1 2 4 5 7 8 

PHI(10) = 4
1 3 7 9 

PHI(11) = 10
1 2 3 4 5 6 7 8 9 10 

---