P2.5.9Euler's totient function

Euler's totient function, $\phi(n)$ , counts the number of positive integers less than or equal to $$n$$ that are relatively prime to $$n$$ . (Two numbers, $$a$$ and $$b$$ , are relatively prime if the only positive integer that divides both of them is 1; that is, if $\mathrm{gcd}(a,b) = 1$ .)

Write a Python program to compute $\phi(n)$ for $1 \le n < 100$ .

[Hint: You could use Euclid's algorithm for the greatest common divisor given in the example to Section 2.5.2.]

Show solution

The code below is one possible approach.

for n in range(1, 100):
    phi = 0
    for k in range(1, n+1):
        a, b = n, k
        while b:
            a, b = b, a % b
        if a == 1:
            phi += 1
    print(phi)