Euler's totient function

#Purpose

Euler’s totient function. For $n \in \mathbb{N}$, it gives $φ(n)$, the number of natural numbers up to $n$ that are coprime to $n$.
When the prime factorization of n is expressed as

,

we calculate using this transformation.

#Time Complexity

$O(\sqrt{n})$

#Usage

1
int res = euler_phi(n);

#Implementation

1
int euler_phi(int n) {
2
  int ret = n;
3
  for (int i = 2; i * i <= n; i++) {
4
    if (n % i == 0) {
5
      ret -= ret / i;
6
      do
7
        n /= i;
8
      while (n % i == 0);
9
    }
10
  }
11
  return n > 1 ? ret - ret / n : ret;
12
}