Sieve of Eratosthenes in GO

Disclaimer
  • The Sieve of Eratosthenes is a well-known algorithm for generating prime numbers.
  • It starts by writing down all numbers from 2 to N (25 in the following): 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
  • The first number (2) is retained and all subsequent multiples of 2 are thrown away:
    2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
  • We then move to the next number in the list (3), keep that and discard all multiples of 3:
    2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
  • This process is repeated for 5:
    2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
  • The numbers that remain are:
    2,3,5,7,11,13,17,19,23
    which are the primes between 2 and 25.
  • There is no need to continue the process beyond √N:
    if there is a non-prime k > √N that has factors a < √N and b > √N such that a × b = k,
    then b would have already been crossed out during the a sweep.
  • For example 22 = 2 × 11, so there is no need to sweep with 11 since 2 has already crossed out 22.
  • serialSieve.go presents a simple version of the Sieve:

Serial Implementation in GO

/* serialSieve.go */
package main
import ( "fmt"; "os"; "strconv"; "time")
func main() {
   N, _  := strconv.Atoi(os.Args[1])
   start := time.Now()
   Prime := make([]bool, N+1)
   for i := range Prime {
      Prime[i] = true
   }
   for i := 2; i*i <= N; i++ {
      if Prime[i] {
         for j:= i*2; j <= N; j = j+i {
            Prime[j] = false
         }
      }
   }
   elapse := time.Since(start)
   count := 0
   for i := 2; i <= N; i++ {
      if Prime[i] {
         fmt.Printf("%d ", i)
         count++
      }
   }
   fmt.Println("\nNum Primes:", count, 
      "time: ", elapse.Microseconds())
}

A typical output from this program is as follows:

$ go run serialSieve.go 25
2  3  5  7  11  13  17  19  23  
Number of Primes: 9 time:  18

line 5: Sieve all numbers up
to and including N, entered
on command line.
line 6: Note start time.
line 7: Prime is an array of size N+1, to sieve numbers up to and including N.
lines 8–10: Prime initialized to true.
lines 11–17: Sieve 2 ≤ i ≤ √N. If i is prime, set to false all multiples, starting with i × 2.


line 18: Compute elapsed time.
lines 19-25: Print out primes.

line 26-27: Print out number of primes (count) and elapsed time in microseconds.

GO home
Next