# totient.py 
# Fig 6.4

import time
# from gcdrec import gcd
from gcditer import gcd

n = int(input("n=? "))
start_time = time.time()
phi = 0
for i in range(1,n+1):
  if gcd(n,i) == 1:
    phi += 1
print("phi(", n, ")==", phi)
print(f"Elapsed time: {(time.time() - start_time):.2f} secs")