prime-generator/sieve.go

package main

import (
	"bufio"
	"io"
	"strconv"
)

// sieve marks primality for every value in [0, limit] with the sieve of
// Eratosthenes. Index i holds true when i is prime, so the slice is indexed by
// the number itself and positions 0 and 1 stay false.
//
// A limit below 2 has no primes at all; the nil slice ranges as empty.
func sieve(limit int) []bool {
	if limit < 2 {
		return nil
	}

	isPrime := make([]bool, limit+1)
	for i := 2; i <= limit; i++ {
		isPrime[i] = true
	}

	// Composites below p*p already carry a smaller factor, so crossing out can
	// start there, and a p past sqrt(limit) has nothing left to mark.
	for p := 2; p*p <= limit; p++ {
		if isPrime[p] {
			for i := p * p; i <= limit; i += p {
				isPrime[i] = false
			}
		}
	}

	return isPrime
}

// writePrimes writes one prime per line, ascending, and reports how many it
// wrote. The output is buffered because a full run emits tens of millions of
// lines.
func writePrimes(w io.Writer, isPrime []bool) (int, error) {
	bw := bufio.NewWriter(w)

	count := 0
	for n, prime := range isPrime {
		if !prime {
			continue
		}
		if _, err := bw.WriteString(strconv.Itoa(n)); err != nil {
			return count, err
		}
		if err := bw.WriteByte('\n'); err != nil {
			return count, err
		}
		count++
	}

	return count, bw.Flush()
}