python - Computing Eulers Totient Function

Question

I am trying to find an efficient way to compute Euler's totient function.

What is wrong with this code? It doesn't seem to be working.

def isPrime(a):
    return not ( a < 2 or any(a % i == 0 for i in range(2, int(a ** 0.5) + 1)))

def phi(n):
    y = 1
    for i in range(2,n+1):
        if isPrime(i) is True and n % i  == 0 is True:
            y = y * (1 - 1/i)
        else:
            continue
    return int(y)

Answer 1

Here's a much faster, working way, based on this description on Wikipedia:

Thus if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ k ≤ n for which gcd(n, k) = 1.

I'm not saying this is the fastest or cleanest, but it works.

from math import gcd

def phi(n):
    amount = 0        
    for k in range(1, n + 1):
        if gcd(n, k) == 1:
            amount += 1
    return amount