## Plan9: generate primes

Published:

`Plan9 primes`

generates all the primes in a specified
range. It uses wheel
factorization with a bit array. You can
find the code on GitHub
(local cache).

## The wheel

Wheel factorization is done with the primes `2`

,
`3`

, `5`

and `7`

. The
`wheel`

array is prefilled with the gaps between the spokes
modulo \(2*3*5*7=210\). The table can
be generated with (wheel.go):

```
package main
import (
"fmt"
)
func main() {
:= []int{2, 3, 5, 7}
primes := 1
N for _, p := range primes {
*= p
N }
:= 1
prev for i := 3; i <= N; i += 2 {
:= true
ok for _, p := range primes {
if i%p == 0 {
= false
ok break
}
}
if ok {
.Printf("%d ", i-prev)
fmt= i
prev }
}
}
```

Run it with:

```
$ go run wheel.go
10 2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10
```

An interesting optimization is that we don’t check a candidate prime
against each spoke, but we `mark`

all the multiplies of the
spokes as composites within `table`

(which is a bitarray).
This is called wheel sieve.

## The bitarray

Commonly one sees a bitarray implemented as (bitarray.c):

```
void
(unsigned char *a, unsigned int i) {
bitset[i>>3] |= 1 << i&7;
a}
int
(unsigned char *a, unsigned int i) {
bitgetreturn a[i>>3] & (1 << i&7);
}
```

`Plan9 primes`

instead of shifting, indexes inside
`bittab`

.

## See also

- Prichard’s wheel sieve on Programming Praxis
- man modf