eratosthenes_parallel/eratosthenes_parallel.go

package main

import (
	"fmt"
	"os"
	"runtime"
	"strconv"
	"time"
)

type work struct {
	i int64
	n0, n1 int64
}

type result bool

func markMultiples(sieve []uint64, workCh chan work, resultCh chan result) {
	for {
		w := <-workCh
		for j := w.n0; j < w.n1; j += 2 * w.i {
			sieve[j>>7] |= 1 << ((j & 0x7F) >> 1)
		}
		resultCh <- true
	}
}

func main() {
	n, err := strconv.ParseInt(os.Args[1], 10, 64)
	if err != nil {
		panic(err)
	}
	nCpus := int64(runtime.NumCPU())
	t0 := time.Now()
	sieve := make([]uint64, (n>>7)+1)
	workCh := make(chan work)
	resultCh := make(chan result)
	var i int64
	for i = 0; i < nCpus; i++ {
		go markMultiples(sieve, workCh, resultCh)
	}
	var found int64
	i = 2
	found++
	for i = 3; i < n; i += 2 {
		if (sieve[i>>7] & (1 << ((i & 0x7F) >> 1))) == 0 {
			found++

			p := nCpus
			var jnext int64
			// XXX - i * i can overflow.
			// bail out before that happens
			if n / i < i {
				continue;
			}
			workers := 0
			for j := i * i; j < n; j = jnext {
				jnext = ((n-j)/(2*i)/p+1)*(2*i) + j
				if jnext > n {
					jnext = n
				}
				workCh <-work{ i, j, jnext }
				workers++
				p--
			}
			for k  := 0; k < workers; k++ {
				_ = <-resultCh
			}
		}
	}
	d := time.Since(t0)
	fmt.Println()
	fmt.Println(found, "primes found in", d)

}