summaryrefslogtreecommitdiff
path: root/go/sieve/sieve.go
blob: 3f69c0344643c678182e4607c3f3cdcd6c83f325 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package sieve

func Sieve(n int) []int {
	p := make([]int, n-1)
	// initialize
	for i := range p {
		p[i] = i + 2
	}
	// sieve
	var ret []int
	for _, v := range p {
		if v != 0 {
			for i := 2*v - 2; i < len(p); i += v {
				p[i] = 0
			}
			ret = append(ret, v)
		}
	}
	return ret
}