Intermediate Exercism • go

Sieve

Challenge Overview

Use the Sieve of Eratosthenes to find all the primes from 2 up to a given number.

Introduction

You bought a big box of random computer parts at a garage sale. You’ve started putting the parts together to build custom computers.

You want to test the performance of different combinations of parts, and decide to create your own benchmarking program to see how your computers compare. You choose the famous “Sieve of Eratosthenes” algorithm, an ancient algorithm, but one that should push your computers to the limits.

Instructions

Your task is to create a program that implements the Sieve of Eratosthenes algorithm to find all prime numbers less than or equal to a given number.

A prime number is a number larger than 1 that is only divisible by 1 and itself. For example, 2, 3, 5, 7, 11, and 13 are prime numbers. By contrast, 6 is not a prime number as it not only divisible by 1 and itself, but also by 2 and 3.

To use the Sieve of Eratosthenes, first, write out all the numbers from 2 up to and including your given number. Then, follow these steps:

Find the next unmarked number (skipping over marked numbers). This is a prime number.
Mark all the multiples of that prime number as not prime.

Repeat the steps until you’ve gone through every number. At the end, all the unmarked numbers are prime.

The Sieve of Eratosthenes marks off multiples of each prime using addition (repeatedly adding the prime) or multiplication (directly computing its multiples), rather than checking each number for divisibility.

The tests don't check that you've implemented the algorithm, only that you've come up with the correct primes.

Example

Let’s say you’re finding the primes less than or equal to 10.

Write out 2, 3, 4, 5, 6, 7, 8, 9, 10, leaving them all unmarked.
```
2 3 4 5 6 7 8 9 10
```
2 is unmarked and is therefore a prime. Mark 4, 6, 8 and 10 as “not prime”.
```
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
```
3 is unmarked and is therefore a prime. Mark 6 and 9 as not prime (marking 6 is optional - as it’s already been marked).
```
2 3 [4] 5 [6] 7 [8] [9] [10]
  ↑
```
4 is marked as “not prime”, so we skip over it.
```
2 3 [4] 5 [6] 7 [8] [9] [10]
     ↑
```
5 is unmarked and is therefore a prime. Mark 10 as not prime (optional - as it’s already been marked).
```
2 3 [4] 5 [6] 7 [8] [9] [10]
        ↑
```

6 is marked as “not prime”, so we skip over it.

2 3 [4] 5 [6] 7 [8] [9] [10]
           ↑

7 is unmarked and is therefore a prime.

2 3 [4] 5 [6] 7 [8] [9] [10]
              ↑

8 is marked as “not prime”, so we skip over it.

2 3 [4] 5 [6] 7 [8] [9] [10]
                 ↑

9 is marked as “not prime”, so we skip over it.

2 3 [4] 5 [6] 7 [8] [9] [10]
                     ↑

10 is marked as “not prime”, so we stop as there are no more numbers to check.

2 3 [4] 5 [6] 7 [8] [9] [10]
                         ↑

You’ve examined all the numbers and found that 2, 3, 5, and 7 are still unmarked, meaning they’re the primes less than or equal to 10.

Dig Deeper

Slice of bools

Slice of `bool`s

// Package sieve is a small library for finding prime numbers
package sieve

// Sieve calculates and returns prime numbers up to the limit
func Sieve(limit int) []int {
	composite := make([]bool, limit+1)
	primes := make([]int, limit/2)
	primeIndex := 0

	for number := 2; number <= limit; number++ {
		if !composite[number] {
			primes[primeIndex] = number
			primeIndex++
			for idx := number + number; idx <= limit; idx += number {
				composite[idx] = true
			}
		}
	}
	return primes[:primeIndex]
}

This approach starts by using the make function to define the slice which will keep track of the composite numbers. The length of limit+1 is used so that the slice does not have to be reallocated. The bool values are initialized to their zero false value.

Similarly, the slice to keep track of primes is also defined with a length, which is set to half of the number being calculated up to, since at least half of the numbers will be even and so not prime. An index into the slice of primes is set for 0.

Since values less than 2 are not prime, the iteration of the outer for loop begins at 2. If the number being iterated is not a composite number, then the element in the slice of primes at the prime index is set to that number, and the prime index is incremented.

Since any number evenly divisible by that prime is not prime, the inner for loop iterates from the prime plus itself, setting each of those numbers to true for being a composite number.

After the outer loop is done, a slice of the primes slice up to but not including the prime index is returned.

For example if limit is 2, then the slice of primes would be made with a length of 1. The element at index 0 would be set to 2 and the prime index incremented to 1. The slice of primes would be sliced from the beginning up to but not including the element at index 1 (good, since index 1 is beyond the length of the slice), and []int{2} would be returned.

if limit is 10, then the slice of primes would be made with a length of 5. The last prime would be 7. The element at index 3 would be set to 7 and the prime index incremented to 4. The slice of primes would be sliced from the beginning up to but not including the element at index 4, and []int{2, 3, 5, 7} would be returned.

Source: Exercism go/sieve