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