parallelsieve.go

package main

import (
	"fmt"
	"sync"
)

func main() {
	// Create our stream of ints up to the threshold
	// This channel is closed by the generate goroutine
	// when all of the ints have been produced.
	ints := generate(255000)

	// Our channel for the primes
	primes := make(chan int)

	var wg sync.WaitGroup

	// Create 50 worker goroutines to filter the stream
	// of ints. They will produce output on the primes
	// channel. They will also call wg.Done when the
	// ints channel has been closed.
	for i := 0; i <= 50; i++ {
		wg.Add(1)
		go filter(ints, primes, &wg)
	}

	// Start a goroutine to wait for the filter worker
	// routines to finish. Once they are done we can
	// close the primes channel so our for range below
	// will finish.
	go func() {
		wg.Wait()
		close(primes)
	}()

	// Loop over the filtered primes
	for i := range primes {
		fmt.Println(i)
	}
}

// generate creates its own channel to produce the stream of ints
// this way it can control the point at which it is closed. Only
// the recv side of the channel is returned for the caller to
// read from.
func generate(thresh int) <-chan int {
	out := make(chan int)

	go func() {
		defer close(out)
		for i := 2; i <= thresh; i++ {
			out <- i
		}
	}()

	return out
}

// filter reads from in until it is closed by the generate routine
// if the received int is a prime, it is written to the out channel
// once the in channel has been closed the function will return and
// call wg.Done()
func filter(in <-chan int, out chan<- int, wg *sync.WaitGroup) {
	defer wg.Done()

	for i := range in {
		if isPrime(i) {
			out <- i
		}
	}
}

// isPrime returns whether the given integer is a prime number or not.
func isPrime(n int) bool {
	if n <= 1 {
		return false
	}

	for i := 2; i <= n/2; i++ {
		if n%i == 0 {
			return false
		}
	}

	return true
}