genkaim

Definition#

The Euler's Totient Function is a function that counts the number of positive integers less than or equal to $n$ that are coprime to $n$. It is denoted as $\phi(n)$.

example

$\phi(2) = 1$, (1)
$\phi(3) = 2$, (1, 2)
$\phi(4) = 2$, (1, 3)
$\phi(5) = 4$, (1, 2, 3, 4)
$\phi(6) = 2$, (1, 5)

Formula#

Conclusion#

Assuming the prime factorization of $n$ is $p_1^a \times p_2^b \times ... \times p_m^k$ ($p_i$ is a prime factor), the Euler's Totient Function can be calculated using the formula:
$\phi(n) = n \times (1- \cfrac{1}{p_1} ) \times (1- \cfrac{1}{p_2} ) \times ... \times (1-\cfrac{1}{p_m})$

Derivation#

First, if a number $x$ is coprime to $n$, it means that they do not have any common prime factors, i.e., $x$ cannot have prime factors such as $p_1$, $p_2$, ..., $p_m$.
So, the number of integers in the range $1...n$ that have $p_1$ as a prime factor is $\cfrac{n}{p_i}$.
Similarly, for each prime factor $p_i$, the number of integers in the range $1...n$ that have $p_i$ as a prime factor is $\cfrac{n}{p_i}$.
Obviously, the number of integers without the prime factor $p_i$ is $n - \sum(\cfrac{n}{p_i})$.

By adding the numbers that were subtracted repeatedly, we can use the principle of inclusion-exclusion to obtain:

• Copy$$$$

=n(1- \cfrac{1}{p_1}) \times (1-\cfrac{1}{p_2})...(1-\cfrac{1}{p_m})$$

Naive Algorithm#

1#

According to the definition, directly enumerate the number of integers in the range $1...n$ that are coprime to $n$ and have the greatest common divisor of 1.

  for(int i=1; i<=n; i++)
    ans += gcd(n, i)==1;

2#

According to the formula

$\phi(n) = n \times (1- \cfrac{1}{p_1} ) \times (1- \cfrac{1}{p_2} ) \times ... \times (1-\cfrac{1}{p_m})$

Loop through the prime factors and calculate ans=ans*(1-1/pi), i.e., ans-= ans/pi

  ans = n;
  for(int i=2; i*i<=n; i++) {
    if(n%i==0) {
      ans -= ans/i;
      while(n%i==0) n/=i;
    }
  }
  if(n>1) ans -= ans/n;

Sieve Method#

Eratosthenes Sieve Method#

According to the definition of the Euler's Totient Function, $\phi(x)=x \times (1- \cfrac{1}{p_i})$

The principle of the Eratosthenes Sieve Method is to sieve all multiples of the prime number $p_i$, indicating that $j \times p_i$ has a prime factor $p_i$, so it can be calculated using the formula mentioned above.

• First, phi[x] = x
• For each multiple j of the prime number $p_i$, phi[j] *= (1-1/pi), which means phi[j] -= phi[j]/pi
  • If for some i, phi[i] != i, it means it has been sieved before and is a composite number

void sieve(int mx) {
  for(int i=1; i<=mx; i++)
    phi[i] = i;
  for(int i=2; i<=mx; i++) {
    if(phi[i] != i) continue;
    for(int j=i; j<=mx; j+=i)
      phi[j] -= phi[j]/i;
  }
}

Euler's Sieve Method#

For a prime number $p_i$, there are two cases to consider:

1. If it is a prime factor of x, then for $x \times p_i$, pi has already been calculated in the Euler's Totient Function $(1-\cfrac{1}{p_i})$, so we have: $\phi(x \times p_i) = \phi(x) \times p_i$
2. If it is not a prime factor of x, then for $x \times pi$, there is an additional prime factor, so we have: $\phi(x \times p_i) = \phi(x) \times p_i \times (1- \cfrac{1}{p_i}) = \phi(x) \times (p_i - 1)$

Combining with the Euler's Sieve Method, we can obtain the code to calculate phi[x].

void sieve(int mx) {
  phi[1] = 1;
  for(int i=2; i<=mx; i++) {
    if(!notPrime[i]) {
      p[++last] = i;
      phi[i] = i-1;
    }
    for(int j=1; j<=last; j++) {
      int t = i * p[j];
      if(t>=mx) break;
      notPrime[t] = true;
      if(i % p[j]==0) {
        phi[t] = phi[i] * p[j];
        break;
      } else
       phi[t]= phi[i] * (p[j]-1);
    }
  }
}