factors/mtc.go


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

package factors

// MTC returns the multiplication table complexity of a radix n.
// This is an estimate of how difficult it is to learn a radix's
// multiplication table.
func MTC(n uint) uint {
	mtc := uint(0)
	for i := uint(2); i <= n - 2; i++ {
		mtc += n / gcd(i, n)
	}
	return mtc
}

func gcd(a, b uint) uint {
	for b > 0 {
		a, b = b, a % b
	}
	return a
}