Euler's totient exactly k times
Do prime factorization

Your current phi() function is correct but slow.  You would do better by finding the prime factorization of n and using the prime factors to calculate phi.  Your current phi() takes \$O(n)\$ time, but a prime factorization takes \$O(\sqrt n)\$ time.

Stop at one

At some point, if k is large, you will reach n of 1.  At that point you can stop because phi(1) = 1.  Actually if at any point k &gt;= n, the answer should be 1 because phi(n) reduces n by at least 1.