Sieve of Eratosthenes

Most of us have heard of the sieve of Eratosthenes as a means of generating small prime numbers. Essentially write down all numbers up to \(N\), then cross out all multiples of \(2\), then multiples of \(3\), etc, and we are left with the prime numbers. This is illustrated for \(N=100\) in the table below.

The beauty of this approach is that we only need to do the crossing out for primes less than \( \sqrt N \) and, for prime \(p\) we start crossing out at \(p^2\) and loop through using multiples of \(p\) so there is less work to do for larger primes.

However we can also use the same approach to generate the factors of all composite numbers up to \(N\). Instead of crossing out a number we simply replace it with the prime that generates this crossing out. This is obviously the lowest factor so it is easy to use the grid to generate the factors. Take the composite number \(54\) as an example. To see this press “Change” in the below table so that the label reads “Generate primes and factors”, now press “Start”, then “End” to show the completed table.

  1. \(54 \rightarrow 2\)
  2. \(54/2 = 27 \rightarrow 3 \)
  3. \(27/3 = 9 \rightarrow 3 \)
  4. \(9/3 = 3 \quad \quad \) (prime)
  5. Prime factors are \(2 \times 3 \times 3 \times 3 \quad \text{ or } 2 \times 3^3 \)
Sieve of Eratosthenes

Sieve of Eratosthenes

Number of Rows: Number of Cols: