Euler’s totient function

Trong lí thuyết số, Phi hàm Euler của số nguyên dương n được định nghĩa là số các số nguyên dương thỏa mãn 2 điều kiện sau:

• Nhỏ hơn hoặc bằng n.
• Nguyên tố cùng nhau với n( Hai số được gọi là nguyên tố cùng nhau khi ước chung lớn nhất của chúng là 1).

Cho số nguyên n, hãy tìm giá trị phi hàm Euler của n.

Ví dụ:

• Nếu n = 5 thì Eulerfunction(5) = 4.

Giải thích: Các số nguyên dương nhỏ hơn n = 5 và nguyên tố cùng nhau với n là 1, 2, 3, 4 => có 4 số thỏa mãn.

• Nếu n = 20 thì Eulerfunction(20) = 8.

Giải thích: Các số nguyên dương nhỏ hơn n = 20 và nguyên tố cùng nhau với n là 1, 3, 7, 9, 11, 13, 17, 19 => có 8 số thỏa mãn.

Đầu vào/Đầu ra:

• [Giới hạn thời gian chạy] 0.5 giây với C++, 3 giây với Java và C#, 4s với Python, Js, 4s với Go.
• [Đầu vào] Long n
  0 < n < 1010
• [Đầu ra] long
  Hãy trả về giá trị phi hàm Euler của n