From c43f8ced883a27f7e6cc8a90ac5c0c87bba6b052 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Tue, 30 Aug 2016 03:17:30 +0200 Subject: Solve factors --- go/prime-factors/README.md | 48 +++++++++++++++++++++++++++++++++++ go/prime-factors/primefactors.go | 16 ++++++++++++ go/prime-factors/primefactors_test.go | 48 +++++++++++++++++++++++++++++++++++ 3 files changed, 112 insertions(+) create mode 100644 go/prime-factors/README.md create mode 100644 go/prime-factors/primefactors.go create mode 100644 go/prime-factors/primefactors_test.go (limited to 'go') 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) + } + } +} -- cgit v1.2.3