- The Sieve of Eratosthenes is a well-known algorithm for generating prime numbers.
- It starts by writing down all numbers from 2 to
(25 in the following):*N***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*that has factors*√N*<**a**and*√N*>**b**such that*√N*,**a**×**b**=**k**

thenwould have already been crossed out during the**b**sweep.**a** - 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:**is an

*Prime**of size*

**array***N+1*, to sieve numbers up to and

*including*

*N.*

**lines 8–10:**

**Prime**initialized to true.

**lines 11–17:**Sieve 2 ≤

*i*≤

**. If**

*√N**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.