primes below n, no allocations past the sieve
0
sieve.go
1package main
2
3import "fmt"
4
5func sieve(n int) []int {
6 composite := make([]bool, n+1)
7 var primes []int
8 for i := 2; i <= n; i++ {
9 if composite[i] {
10 continue
11 }
12 primes = append(primes, i)
13 for j := i * i; j <= n; j += i {
14 composite[j] = true
15 }
16 }
17 return primes
18}
19
20func main() {
21 fmt.Println(sieve(50))
22}
Only correct because the outer loop skips composites — otherwise it would miss factors.
Starting the inner loop at
i*iis the bit everyone forgets.