Euler's Totient

The Co-Prime Count

The Euler's Totient Function $\phi(n)$ counts the integers $k$ such that $1 le k le n$ and $gcd(n, k) = 1$. Example: $\phi(9)$. Numbers co-prime to 9 are {1, 2, 4, 5, 7, 8}. So $\phi(9) = 6$.

The Assignment

Your function receives a parameter n.

1. Initialize result to n.
2. Use a loop to find prime factors of n.
3. For every prime factor p, update result = result * (1 - 1/p).
4. Print the final integer result.