output_description: The number of totatives in a line.
input_description: n
      
  
  An integer n (1 ≤ n ≤ 1000000000).
attempt: a = []
  n = int(input())
  s = n**0.5
  while n % 2 == 0 and n > 3:
      a += [2]
      n //= 2
  d = 3
  while s > d and n > d:
      if n % d > 0:
          d += 2
      else:
          a += [d]
          n //= d
  a += [n]
  p = 1
  for f in set(a):
      p *= f ** a.count(f) * (1 - 1 / f)
  print(int(p))
  
problem_description: Euler's Phi Function
  
    
  
  For given integer n, count the totatives of n, that is, the positive integers
  less than or equal to n that are relatively prime to n.
samples: [{"input": "6", "output": "2"}, {"input": "1000000", "output": "400000"}]