Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 244
Good morning! Here's your coding interview problem for today.

This problem was asked by Square.

The Sieve of Eratosthenes is an algorithm used to generate all prime numbers smaller than N. The method is to take increasingly larger prime numbers, and mark their multiples as composite.

For example, to find all primes less than 100, we would first mark [4, 6, 8, ...] (multiples of two), then [6, 9, 12, ...] (multiples of three), and so on. Once we have done this for all primes less than N, the unmarked numbers that remain will be prime.

Implement this algorithm.

Bonus: Create a generator that produces primes indefinitely (that is, without taking N as an input).

Pull request:
Day244
Resolves #503 

Patch:
diff --git a/README.md b/README.md
index 8f6f111..b2cac03 100644
--- a/README.md
+++ b/README.md
@@ -254,3 +254,4 @@ problems from
 * [Day 240](https://github.com/vaskoz/dailycodingproblem-go/issues/492)
 * [Day 241](https://github.com/vaskoz/dailycodingproblem-go/issues/493)
 * [Day 242](https://github.com/vaskoz/dailycodingproblem-go/issues/498)
+* [Day 244](https://github.com/vaskoz/dailycodingproblem-go/issues/503)
diff --git a/day244/problem.go b/day244/problem.go
new file mode 100644
index 0000000..8a40a67
--- /dev/null
+++ b/day244/problem.go
@@ -0,0 +1,51 @@
+package day244
+
+import "math"
+
+// SieveOfEratosthenes returns all the primes strictly less than n.
+// If n happens to be a prime, it will NOT be returned in the result.
+// Runtime is O(N log log N)
+func SieveOfEratosthenes(n int) []int {
+	if n < 2 {
+		return nil
+	}
+	isNotPrime := make([]bool, n)
+	isNotPrime[0], isNotPrime[1] = true, true
+	for i := 2; i <= int(math.Sqrt(float64(n))); i++ {
+		if !isNotPrime[i] {
+			for j := i * i; j < n; j += i {
+				isNotPrime[j] = true
+			}
+		}
+	}
+	var primes []int
+	for p, notPrime := range isNotPrime {
+		if !notPrime {
+			primes = append(primes, p)
+		}
+	}
+	return primes
+}
+
+// SieveOfEratosthenesGenerator returns primes indefinitely.
+// Only runs when the channel is read for more primes.
+func SieveOfEratosthenesGenerator() <-chan int {
+	primes := make(chan int)
+	go func() {
+		n := 2
+		composites := make(map[int][]int)
+		for {
+			if _, found := composites[n]; !found {
+				primes <- n
+				composites[n*n] = []int{n}
+			} else {
+				for _, prime := range composites[n] {
+					composites[n+prime] = append(composites[n+prime], prime)
+				}
+				delete(composites, n)
+			}
+			n++
+		}
+	}()
+	return primes
+}


Test patch:
diff --git a/day244/problem_test.go b/day244/problem_test.go
new file mode 100644
index 0000000..91aaa15
--- /dev/null
+++ b/day244/problem_test.go
@@ -0,0 +1,60 @@
+package day244
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	n      int
+	primes []int
+}{
+	{100, []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}},
+	{2, nil},
+	{1, nil},
+	{0, nil},
+}
+
+func TestSieveOfEratosthenes(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if primes := SieveOfEratosthenes(tc.n); !reflect.DeepEqual(primes, tc.primes) {
+			t.Errorf("Expected %v, got %v", tc.primes, primes)
+		}
+	}
+}
+
+func BenchmarkSieveOfEratosthenes(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SieveOfEratosthenes(tc.n)
+		}
+	}
+}
+
+func TestSieveOfEratosthenesGenerator(t *testing.T) {
+	t.Parallel()
+	primesToThousand := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
+		71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
+		173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271,
+		277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
+		389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
+		499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613,
+		617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
+		739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,
+		859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
+		991, 997}
+	primeGenerator := SieveOfEratosthenesGenerator()
+	for _, prime := range primesToThousand {
+		if p := <-primeGenerator; p != prime {
+			t.Errorf("Expected %v, got %v", prime, p)
+		}
+	}
+}
+
+func BenchmarkSieveOfEratosthenesGenerator(b *testing.B) {
+	primeGenerator := SieveOfEratosthenesGenerator()
+	for i := 0; i < b.N; i++ {
+		<-primeGenerator
+	}
+}