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