#calculates the euler phi function

def phi(n):
   i=2
   result=n
   while(i**2<=n):
       if(n%i==0):
           result=result-result/i
       while(n%i==0):
           n=n/i
       i=i+1
   if (n>1):
       result=result-result/n
   return result