factors/totative.go


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

package factors

// Totient calculates the number of numbers less than n that
// are totatives of n (share no factors with n)
func Totient(n uint) uint {
	if n == 0 {
		return 0
	}

	primeFactorization := PrimeFactorize(n)
	num, denom := uint(1), uint(1)

	for p := range primeFactorization.exponents {
		num *= p - 1
		denom *= p
	}

	return num * (n / denom)
}