Sieve of Eratosthenes in Golang - O(n(log(log(n))))

prime_number_sieve.go

package main

import "fmt"

func sieve(n uint64) []bool {
  primeBits := make([]bool, n-2)
  
  for i := uint64(2); i < n; i++ {
    for j := i; (i*j)-2 < n-2; j++ {
      primeBits[(i*j)-2] = true
    }
  }

  return primeBits
}

func getPrimes(sieve []bool) []uint64 {
  n := uint64(len(sieve))
  primes := make([]uint64, 0);
  
  for i := uint64(0); i < n; i++ {
    if !sieve[i] {
      primes = append(primes, i+2)
    }
  }

  return primes
}

func main() {
  var n uint64
  
  for {
    _, err := fmt.Scanf("%d", &n)
    if err != nil {
      panic("Unexpected input encountered")
    }
    
    if n == 0 {
      break
    }
    
    sieve := sieve(n)
    primes := getPrimes(sieve)
    for i := 0; i < len(primes); i++ {
      fmt.Println(primes[i])
    }
  }
}