## Sieve of Eratosthenes

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

 = true
 = true
 = true. ....  = true```

Then 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
 = false
2*3 = 6
 = false
2*4 = 8
 = false
...```

and finally for all elements which have a true against it I add it to the `int[]` and return it.