# Prime sieve (in Go ofcourse)

## November 24, 2009

### programming

After reading up on the prime sieve, and playing with Go for the past week I thought needed to implement this algorithm in Go and make it parallel.

I want to create a set (n in 2..N) goroutines. Each of these routines will check if it can divide a number (i) by n (integer division). If so the number i is not prime, otherwise it is given to the next goroutine. Communication between the goroutines is done via channels as in this example.

# Sieve

In this small example I have 5 goroutines, and we give it the number 3 and 4. The table shows the reminder when dividing by n.

``````            n = 2   3   4   5  ... ...
-------------------------------------------
i  = 3 % n      1   0   3   3   3   3   ...
i  = 4 % n      0   1   0   4   4   3   ...
``````

From here we see that i = 3 is prime, because it has an 1 in the column where n = 2, i = 4 is not prime, because it has a zero in the column where n = 2.

The algorithm for each goroutine thus becomes (in pseudo code):

``````function(n, i) {
if i == 0 then copy to next goroutine; return
if n >= i then copy to next goroutine; return

// test for primeness, if not prime return the *magic*
// number 0
if i % n == 0 then
// not prime
give 0 to the next goroutine
fi

give i to the next goroutine
}
``````

Or in Go’s syntax:

``````func f(left, right chan int, n int) {
i := <-right;
if i == 0 || n >= i {
left <- i;
return;
}
if i%n == 0 {
left <- 0;
return;
}
left <- i;
}
``````

# Main

The rest of the Go program should setup the goroutines, channels and handle the flags. N - 1 goroutines are set up, and each is connected to its neighbor.

Even nicer would be to really do this in parallel, i.e. send i to all goroutines, and then just see if one of them returned zero. If none of them do, its a prime. For now the following must suffice.

In Go code:

``````leftmost := make(chan int);
var left, right chan int = nil, leftmost;
for n := 0; n < *prime-1; n++ {
left, right = right, make(chan int);
go f(left, right, *prime-n);
}
right <- *prime;        // bang!
x := <-leftmost;        // wait for completion
fmt.Println(x);
``````

This outputs 0 when the number tested is not prime, it outputs the number itself given when it is prime.

``````% ./sieve -p 32
0           # not prime

% ./sieve -p 11
11          # prime ;-)
``````

# Complete listing

``````package main

import (
"flag";
"fmt";
"os";
)

var prime = flag.Int("p", 13, "test for primeness")

func f(left, right chan int, n int) {
i := <-right;
if i == 0 || n >= i {
left <- i;
return;
}
if i%n == 0 {
left <- 0;
return;
}
left <- i;
}

func main() {
flag.Parse();

if *prime < 2 {
os.Exit(1);
}

leftmost := make(chan int);
var left, right chan int = nil, leftmost;
for n := 0; n < *prime-1; n++ {
left, right = right, make(chan int);
go f(left, right, *prime-n);
}
right <- *prime;        // bang!
x := <-leftmost;        // wait for completion
fmt.Println(x);
}
``````
Misc