summaryrefslogtreecommitdiff
path: root/go
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2016-08-30 03:17:30 +0200
committerDimitri Sokolyuk <demon@dim13.org>2016-08-30 03:17:30 +0200
commitc43f8ced883a27f7e6cc8a90ac5c0c87bba6b052 (patch)
treecd055e648d3f102a2016bda756acef7e5aec6ce8 /go
parent8e485c07945442cb64b8b0cdf48d17f9a1d27e4d (diff)
Solve factors
Diffstat (limited to 'go')
-rw-r--r--go/prime-factors/README.md48
-rw-r--r--go/prime-factors/primefactors.go16
-rw-r--r--go/prime-factors/primefactors_test.go48
3 files changed, 112 insertions, 0 deletions
diff --git a/go/prime-factors/README.md b/go/prime-factors/README.md
new file mode 100644
index 0000000..c9002fb
--- /dev/null
+++ b/go/prime-factors/README.md
@@ -0,0 +1,48 @@
+# Prime Factors
+
+Compute the prime factors of a given natural number.
+
+A prime number is only evenly divisible by itself and 1.
+
+Note that 1 is not a prime number.
+
+## Example
+
+What are the prime factors of 60?
+
+- Our first divisor is 2. 2 goes into 60, leaving 30.
+- 2 goes into 30, leaving 15.
+ - 2 doesn't go cleanly into 15. So let's move on to our next divisor, 3.
+- 3 goes cleanly into 15, leaving 5.
+ - 3 does not go cleanly into 5. The next possible factor is 4.
+ - 4 does not go cleanly into 5. The next possible factor is 5.
+- 5 does go cleanly into 5.
+- We're left only with 1, so now, we're done.
+
+Our successful divisors in that computation represent the list of prime
+factors of 60: 2, 2, 3, and 5.
+
+You can check this yourself:
+
+- 2 * 2 * 3 * 5
+- = 4 * 15
+- = 60
+- Success!
+
+To run the tests simply run the command `go test` in the exercise directory.
+
+If the test suite contains benchmarks, you can run these with the `-bench`
+flag:
+
+ go test -bench .
+
+For more detailed info about the Go track see the [help
+page](http://exercism.io/languages/go).
+
+## Source
+
+The Prime Factors Kata by Uncle Bob [http://butunclebob.com/ArticleS.UncleBob.ThePrimeFactorsKata](http://butunclebob.com/ArticleS.UncleBob.ThePrimeFactorsKata)
+
+## Submitting Incomplete Problems
+It's possible to submit an incomplete solution so you can see how others have completed the exercise.
+
diff --git a/go/prime-factors/primefactors.go b/go/prime-factors/primefactors.go
new file mode 100644
index 0000000..d8cc3d6
--- /dev/null
+++ b/go/prime-factors/primefactors.go
@@ -0,0 +1,16 @@
+package prime
+
+const testVersion = 2
+
+func Factors(n int64) []int64 {
+ f := []int64{}
+ for i := int64(2); n > 1; {
+ if n%i == 0 {
+ n /= i
+ f = append(f, i)
+ } else {
+ i++
+ }
+ }
+ return f
+}
diff --git a/go/prime-factors/primefactors_test.go b/go/prime-factors/primefactors_test.go
new file mode 100644
index 0000000..40bbed8
--- /dev/null
+++ b/go/prime-factors/primefactors_test.go
@@ -0,0 +1,48 @@
+package prime
+
+// Return prime factors in increasing order
+
+import (
+ "reflect"
+ "testing"
+)
+
+const targetTestVersion = 2
+
+var tests = []struct {
+ input int64
+ expected []int64
+}{
+ {1, []int64{}},
+ {2, []int64{2}},
+ {3, []int64{3}},
+ {4, []int64{2, 2}},
+ {6, []int64{2, 3}},
+ {8, []int64{2, 2, 2}},
+ {9, []int64{3, 3}},
+ {27, []int64{3, 3, 3}},
+ {625, []int64{5, 5, 5, 5}},
+ {901255, []int64{5, 17, 23, 461}},
+ {93819012551, []int64{11, 9539, 894119}},
+}
+
+func TestPrimeFactors(t *testing.T) {
+ if testVersion != targetTestVersion {
+ t.Fatalf("Found testVersion = %v, want %v", testVersion, targetTestVersion)
+ }
+ for _, test := range tests {
+ actual := Factors(test.input)
+ if !reflect.DeepEqual(actual, test.expected) {
+ t.Errorf("prime.Factors(%d) = %v; expected %v",
+ test.input, actual, test.expected)
+ }
+ }
+}
+
+func BenchmarkPrimeFactors(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ for _, test := range tests {
+ Factors(test.input)
+ }
+ }
+}