Eulers Fonksiyonu ile girdi sayısına göre tekrarlayarak sonucu nasıl bulabilirim

[Stayy]

Selam arkadaşlar, bi konuda desteğe ihtiyacım var. Hackerearth sitesinde Bi Python sorusunda bi kaç soru çözmem gerekiyor ama yapamıyorum. Daha doğrusu programım doğru fakat test denemeleri yaparken site deneme sayılarını milyon milyar veriyor. Dolayısıyla testlerin bi kısmını geçerken bi kısmında zaman aşımına veya bellek aşımına uğruyor. Programı yeterinde minimalize ettim ama daha fazla edersem çalışmıyor, yardım edebilecek Python yazılımcısı var mı?

Soru kullanıcının girdiği sayıyı Euler fonksiyonunu kullanıcının girdiği tekrar sayısına göre tekrarlayarak en son sonucu bulmak.

from math import gcd
import math
n,k=input().split()
n,k=int(n),int(k)

# Python 3 program to calculate
# Euler's Totient Function
# using Euler's product formula
 
def phi(a) :
 
    result = a   # Initialize result as n
      
    # Consider all prime factors
    # of n and for every prime
    # factor p, multiply result with (1 - 1 / p)
    p = 2
    while p * p<= a :
 
        # Check if p is a prime factor.
        if a % p == 0 :
 
            # If yes, then update n and result
            while a % p == 0 :
                a = a // p
            result = result * (1.0 - (1.0 / float(p)))
        p = p + 1
        
        
    # If n has a prime factor
    # greater than sqrt(n)
    # (There can be at-most one
    # such prime factor)
    if a > 1 :
        result -= result // a
  #Since in the set {1,2,....,n-1}, all numbers are relatively prime with n
  #if n is a prime number
 
    return int(result)
    
    
 

if n>=1 and n<=10**15 and k<=10**18:
    while k!=0:
        n=phi(n)
        k-=1
print(n)

Son yazdığım kod bu, şuana kadar elimdekinin en iyisi fakat bu bile 10-15 testte zaman aşımına uğruyor.