# 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 {
// too bad
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

ito 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 {
// too bad
left <- 0;
return;
}
left <- i;
}
func main() {
flag.Parse();
if *prime < 2 {
fmt.Fprint(os.Stderr, "You know this already\n");
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);
}
```