Skip to content

Instantly share code, notes, and snippets.

@danielrangelmoreira
Forked from iandioch/totients.go
Created April 23, 2017 16:25
Show Gist options
  • Save danielrangelmoreira/ec50a99cb76221ea436591d510d2dab2 to your computer and use it in GitHub Desktop.
Save danielrangelmoreira/ec50a99cb76221ea436591d510d2dab2 to your computer and use it in GitHub Desktop.
Golang implementation of Euler's totient/phi function
/*
* Go implementation of Euler's product formula to find for the totient function (aka. phi function)
* https://en.wikipedia.org/wiki/Euler's_totient_function#Euler.27s_product_formula
*/
package main
import (
"fmt"
)
func getPrimeFactors(n int, primes []int) map[int]int {
primeFacts := make(map[int]int) // keeps track of prime factor : exponent pairs
for n != 1 {
for i := 0; i < len(primes); i ++ {
if n % primes[i] == 0 {
val, ok := primeFacts[primes[i]]
if !ok {
val = 0
}
primeFacts[primes[i]] = val + 1
n = n/primes[i]
break
}
}
}
return primeFacts
}
func getPrimes(N int) []int {
isComposite := make([]bool, N)
primes := []int{}
for i := 2; i < N; i ++ {
if !isComposite[i] {
primes = append(primes, i)
for x := i+i; x < N; x += i {
isComposite[x] = true
}
}
}
return primes
}
func totient(n int, primes []int) int {
primeFacts := getPrimeFactors(n, primes)
ans := n
for prime := range primeFacts {
ans = ans*(prime-1)/prime
}
return ans
}
func main(){
primes := getPrimes(1000000)
for i:= 2; i <= 1000; i ++ {
fmt.Println(i, totient(i, primes))
}
fmt.Println(36, totient(36, primes))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment