[Golang] Euler's Totient Function


Implementation of Euler's totient function in Go programming language.

Euler's totient function φ(n) counts the positive integers that are relatively prime to n, i.e., the number of positive integers whose GCD (Greatest Common Divisor) [2] with n is 1.

According to above definition, the naive solution to implement φ(n) is as follows:

Run Code on Go Playground

// greatest common divisor (GCD) via Euclidean algorithm
func GCD(a, b uint) uint {
      for b != 0 {
              t := b
              b = a % b
              a = t
      }
      return a
}

// Euler’s Totient Function
func Phi(n uint) uint {
      var result uint = 1
      var i uint
      for i = 2; i < n; i++ {
              if GCD(i, n) == 1 {
                      result++
              }
      }
      return result
}

According to the GeeksforGeeks post [1], there is a better solution based on Euler’s product formula without floating point calculations. I port the solution from C to Go:

Run Code on Go Playground

func Phi(n uint) (result uint) {
      // Initialize result as n
      result = n

      // Consider all prime factors of n and subtract their
      // multiples from result
      var p uint
      for p = 2; p*p <= n; p++ {
              // Check if p is a prime factor.
              if n%p == 0 {
                      // If yes, then update n and result
                      for n%p == 0 {
                              n /= p
                      }
                      result -= (result / p)
              }
      }

      // If n has a prime factor greater than sqrt(n)
      // (There can be at-most one such prime factor)
      if n > 1 {
              result -= (result / n)
      }
      return result
}

Tested on:


References:

[1]Euler's Totient Function - GeeksforGeeks
[2][Golang] Greatest Common Divisor via Euclidean Algorithm