Plan9: generate primes

Published: 2014-12-18

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

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
bitset(unsigned char *a, unsigned int i) {
    a[i>>3] |= 1 << i&7;
}

int
bitget(unsigned char *a, unsigned int i) {
    return a[i>>3] & (1 << i&7);
}

Plan9 primes instead of shifting, indexes inside bittab.

Home — Blog