Add list of factors to output

2 files changed, 67 insertions, 1 deletions

diff --git a/factors/factorize.go b/factors/factorize.go
new file mode 100644
index 0000000..2f7368a
--- /dev/null
+++ b/factors/factorize.go
@@ -0,0 +1,27 @@
+package factors
+
+// Factors returns a number's factors as a slice.
+// The slice is not guaranteed to be in sorted order.
+func Factors(n uint) []uint {
+	if n == 0 {
+		panic("Cannot get factors of 0!")
+	}
+
+	primeFactorization := PrimeFactorize(n)
+
+	factors := []uint{1}
+	for p, e := range primeFactorization.exponents {
+		next_factors := make([]uint, 0, len(factors) * int(e))
+		for _, factor := range factors {
+			for i := uint(0); i <= e; i++ {
+				multiplier := uint(1)
+				for j := uint(0); j < i; j++ {
+					multiplier *= p
+				}
+				next_factors = append(next_factors, factor * multiplier)
+			}
+		}
+		factors = next_factors
+	}
+	return factors
+}
diff --git a/factors/factors_test.go b/factors/factors_test.go
index 472a2e3..a2e81cd 100644
--- a/factors/factors_test.go
+++ b/factors/factors_test.go
@@ -31,7 +31,46 @@ func TestPrimeFactorize(t *testing.T) {
 	}
 }
 
-func mapEquals(a, b map[uint]uint) bool {
+var factorCases = map[uint][]uint{
+	1: []uint{1},
+	2: []uint{1, 2},
+	4: []uint{1, 2, 4},
+	6: []uint{1, 2, 3, 6},
+	10: []uint{1, 2, 5, 10},
+	12: []uint{1, 2, 3, 4, 6, 12},
+	13: []uint{1, 13},
+	15: []uint{1, 3, 5, 15},
+	18: []uint{1, 2, 3, 6, 9, 18},
+	60: []uint{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60},
+}
+
+func TestFactors(t *testing.T) {
+	for i, expected := range factorCases {
+		testname := fmt.Sprintf("%d", i)
+		t.Run(testname, func(t *testing.T) {
+			actual := Factors(i)
+			if !setEquals(expected, actual) {
+				t.Errorf("Factors(%d) = %v, want %v", i, actual, expected)
+			}
+		})
+	}
+}
+
+func setEquals(a, b []uint) bool {
+	// use maps to simulate sets
+	// aSet[a] == true means set contains a, false means not
+	aSet := make(map[uint]bool)
+	bSet := make(map[uint]bool)
+	for _, i := range a {
+		aSet[i] = true
+	}
+	for _, j := range b {
+		bSet[j] = true
+	}
+	return mapEquals(aSet, bSet)
+}
+
+func mapEquals[K comparable, V comparable](a, b map[K]V) bool {
 	for k := range a {
 		if a[k] != b[k] {
 			return false