// Package sieve creates a Sieve of Erastothenes.
package sieve
// Sieve outputs the primes <= limit.
func Sieve(limit int) []int {
	mp := make(map[int]struct{})
	out := make([]int, 0, limit/2)
	for i := 2; i <= limit; i++ {
		for j := i; j <= limit; j += i {
			_, marked := mp[j]
			if j == i && !marked {
				out = append(out, j)
			}
			// mark every _non_ prime if not marked already
			if !marked {
				mp[j] = struct{}{}
			}
		}
	}
	return out
}