output_description: The number of totatives in a line.
input_description: n
      
  
  An integer n (1 ≤ n ≤ 1000000000).
attempt: import math
  
  
  def sieve(n):
      p = [1] * (n + 1)
      p[0] = p[1] = 0
  
      for i in range(math.ceil((n + 1) ** 0.5)):
          if p[i]:
              for j in range(2 * i, len(p), i):
                  p[j] = 0
      return p
  
  
  from itertools import compress, count
  
  
  def prime_factor(n):
      p = sieve(int(n**0.5))
      factor = []
      for pi in compress(count(0), p):
          while n % pi == 0:
              n //= pi
              factor.append(pi)
  
      if n != 1:
          factor.append(n)
      return factor
  
  
  from sys import stdin
  from functools import reduce
  from operator import mul
  from collections import Counter
  
  readline = stdin.readline
  
  print(
      reduce(
          mul,
          (
              pow(p, k) - pow(p, k - 1)
              for p, k in Counter(prime_factor(int(readline()))).items()
          ),
      )
  )
  
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"}]