Lucas Katayama

Prime Sieve

Photo by Clément Hélardot on Unsplash

Prime Sieve

Prime sieve implementation

Lucas Katayama's photo
Lucas Katayama
·

10 min read

Table of contents

Yesterday, I watched a video from Steve Francia and he showed a Prime Sieve implementation written in Go.

Algorithm

The prime sieve is an algorithm to generate prime numbers and, if I understand correctly, is something like this.

You have a Generator that creates sequential integers starting from 2 (the first prime).

Generator
2
3
4
5
6
7
8
9
10
11
12
13

As it generates the numbers, you check if it is a prime and creates a Filter filter out the multiples of that prime

GeneratorFilter 2
2 ->2
33
4-
55
6-
77
8-
99
10-
1111
12-
1313

The next one is 3, which passes the Filter 2 which is a prime, then you create another filter and pass the number ahead:

GeneratorFilter 2Filter 3
2[2]
3 ->3 ->[3]
4
5
6
7
8
9
10
11
12
13

And the same goes on and on:

GeneratorFilter 2Filter 3
2[2]
33[3]
4 ->-
5
6
7
8
9
10
11
12
13
GeneratorFilter 2Filter 3Filter 5
2[2]
33[3]
4-
5 ->5 ->5 ->[5]
6
7
8
9
10
11
12
13
GeneratorFilter 2Filter 3Filter 5
2[2]
33[3]
4-
555[5]
6 ->-
7
8
9
10
11
12
13
GeneratorFilter 2Filter 3Filter 5Filter 7
2[2]
33[3]
4-
555[5]
6-
7 ->7 ->7 ->7 ->[7]
8
9
10
11
12
13
GeneratorFilter 2Filter 3Filter 5Filter 7
2[2]
33[3]
4-
555[5]
6-
7777[7]
8 ->-
9
10
11
12
13
GeneratorFilter 2Filter 3Filter 5Filter 7
2[2]
33[3]
4-
555[5]
6-
7777[7]
8-
9 ->9 ->-
10
11
12
13
GeneratorFilter 2Filter 3Filter 5Filter 7
2[2]
33[3]
4-
555[5]
6-
7777[7]
8-
99-
10 ->-
11
12
13
GeneratorFilter 2Filter 3Filter 5Filter 7Filter 11
2[2]
33[3]
4-
555[5]
6-
7777[7]
8-
99-
10-
11 ->11 ->11 ->11 ->11 ->[11]
12
12
13
13
GeneratorFilter 2Filter 3Filter 5Filter 7Filter 11Filter 11
2[2]
33[3]
4-
555[5]
6-
7777[7]
8-
99-
10-
1111111111[11]
12 ->-
13 ->13 ->13 ->13 ->13 ->13 ->[13]

Implementation

That algorithm can be implemented using goroutines and channels in Go.

Each filter is a goroutine that receives a number through a channel.

If the number is not a multiple and the next filter is not created, then I have a prime. So I printed it and created another filter.

Here is the code presented in the video:

package main

func Generate(ch chan int) {
    for i := 2; ; i++ {
        ch <- i
    }
}

func Filter(src chan<- int, dst <-chan int, prime int) {
    for i := range src {
        if i%prime != 0 {
            dst <- i
        }
    }
}

func main() {
    src := make(chan int)
    go Generate(src)
    for i := 0; i < 100; i++ {
        prime := <-src
        println(prime)
        dst := make(chan int)
        go Filter(src, dst, prime)
        src = dst
    }
}

To understand how the code works in Go, we need to understand:

  • Goroutines

  • Unbuffered channels

  • Call by value/pointers functions

The main concept of the algorithm is explained in the video. But as an early golang developer I didn’t understand what was going on on the main for loop.

So I am going to try to exaplain it here.

Main for loop

  1. The Generate goroutine is running but it stops when it puts a number on an unbuffered channel (ch) [lines 19, 5]

  2. The for makes the first loop (number 2) received by the Generate (now the channel clears and Generate puts another number) [lines 21, 5]

  3. Print it [line 22]

  4. Creates communication with src and dst channels and runs another goroutine for Filter 2 [line 23, 24]

  5. Change pointer from src to dst [line 25]

Here is the interesting part. If you change src to dst it loses reference to the previous src, BUT when you called the Filter function, it already stored a context with the previous src.

So the -> between Generate and Filter 2 (in the previous section) is stored and can be used. Will look something like this:

Generator | - ——— | - 2 | 3 -> | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

When it runs 3 and 4 will look like this:

  • Print [2]
Generator-
2[2]
3 ->
4
5
6
7
8
9
10
11
12
13
  • Creates channel and filter
GeneratorFilter 2
2[2]
3 ->->
4
5
6
7
8
9
10
11
12
13
  • src = dst
GeneratorFilter 2
2[2]
3 ->3 ->
4
5
6
7
8
9
10
11
12
13

Wrapping up

This is a pretty cool algorithm using Concurrency from Golang. It took me time to understand but it helped me to learn a lot about the details of the language.

I hope it can help you.

The code can be found here https://github.com/lucaskatayama/go-prime-sieve

References

golangalgorithms