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 uint32) uint64 {
	mtc := uint64(0)
	for i := uint32(2); i <= n-2; i++ {
		mtc += uint64(n / gcd(i, n))
	}
	return mtc
}

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