# [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)  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 , 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: