Sieve is an ancient and an ingenious way of calculating primes. It recursively eliminates all the multiples of a particular number up till a range and the left overs are essentially primes.
It was just a matter of defining the right data structure and computing the final set of primes
package sieve
import "sort"
// Sieve calculates prime
func Sieve(limit int) (out []int) {
out = make([]int, 0)
myMap := make(map[int]bool, 0)
if limit <= 1 {
return
}
// Populate all the numbers
for i := 2; i <= limit; i++ {
myMap[i] = true
}
// Check the numbers and false all the multiples
for i := 2; i <= limit; i++ {
for j := 2; (j * i) <= limit; j++ {
if myMap[(i * j)] {
myMap[(i * j)] = false
}
}
}
// Append only the positive found
for k := range myMap {
if myMap[k] {
out = append(out, k)
}
}
sort.Ints(out)
return
}I used a map of (int, boolean)to add all the element up to the limit (13 in my example above)
Initial Map has
[2] = true
[3] = true
[4] = true. .... [13] = trueThen I ran a simple for loop to iterate till the limit 13 on the map and mark all the multiples as false.
So it starts with 2 till 13 checking for every multiple and marking it false.
2*2 = 4
[4] = false
2*3 = 6
[6] = false
2*4 = 8
[8] = false
...and finally for all elements which have a true against it I add it to the int[] and return it.
