Sieve of Eratosthenes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

package main

import "fmt"

func fetchFirstPrimeNumbersOf(n int) []int {
  var result []int

  // an integer n > 1
  if n <= 1 {
    return result
  }

  // let A be an array of Boolean values
  isPrime := make([]bool, n)

  // indexed by integers 2 to n,
  // initially all set to true.
  for i := 2; i < n; i++ {
    isPrime[i] = true
  }

  // for i = 2, 3, 4, ..., not exceeding √n do
  for i := 2; i*i < n; i++ {
    // I reverse the conditional check in order to make things a bit pretty

    // if A[i] is true
    if !isPrime[i] {
      continue
    }

    // for j = i^2, (i^2)+i, (i^2)+2i, (i^2)+3i, ..., not exceeding n do
    for j := i * i; j < n; j += i {
      // A[j] := false
      isPrime[j] = false
    }
  }

  // return all i such that A[i] is true.
  for i := 2; i < n; i++ {
    if !isPrime[i] {
      continue
    }

    result = append(result, i)
  }

  return result
}

func main() {
  fmt.Println(fetchFirstPrimeNumbersOf(100))
}