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

```
// 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:

```
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 |