Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
eulers_totient_function.cpp File Reference

C++ Program to find Euler's Totient function. More...

#include <cstdlib>
#include <iostream>
Include dependency graph for eulers_totient_function.cpp:

Functions

uint64_t phiFunction (uint64_t n)
 
int main (int argc, char *argv[])
 Main function.
 

Detailed Description

C++ Program to find Euler's Totient function.

Euler Totient Function is also known as phi function.

\[\phi(n) = \phi\left({p_1}^{a_1}\right)\cdot\phi\left({p_2}^{a_2}\right)\ldots\]

where \(p_1\), \(p_2\), \(\ldots\) are prime factors of n.
3 Euler's properties:

  1. \(\phi(n) = n-1\)
  2. \(\phi(n^k) = n^k - n^{k-1}\)
  3. \(\phi(a,b) = \phi(a)\cdot\phi(b)\) where a and b are relative primes.

Applying this 3 properties on the first equation.

\[\phi(n) = n\cdot\left(1-\frac{1}{p_1}\right)\cdot\left(1-\frac{1}{p_2}\right)\cdots\]

where \(p_1\), \(p_2\)... are prime factors. Hence Implementation in \(O\left(\sqrt{n}\right)\).
Some known values are:

  • \(\phi(100) = 40\)
  • \(\phi(1) = 1\)
  • \(\phi(17501) = 15120\)
  • \(\phi(1420) = 560\)

Function Documentation

◆ phiFunction()

uint64_t phiFunction ( uint64_t  n)

Function to caculate Euler's totient phi

32  {
33  uint64_t result = n;
34  for (uint64_t i = 2; i * i <= n; i++) {
35  if (n % i == 0) {
36  while (n % i == 0) {
37  n /= i;
38  }
39  result -= result / i;
40  }
41  }
42  if (n > 1)
43  result -= result / n;
44  return result;
45 }