Introduction
The sieve of Eratosthenes is an elegant algorithm used to find all prime numbers up to a certain limit. First described in a manuscript over 2000 years ago and is effective today as it was then. After seeing a visualisation of pi I decided to try my hand at visualising prime numbers. Having done mostly back-end and command line work in C++ this was a good opportunity to learn about rendering graphics.
The algorithm
When you have eliminated all which is impossible, then whatever remains, however improbable, must be the truth.
Since a prime number is any natural number that is only divisible by one and itself, enumerating over the multiples of all numbers and marking them leaves only prime numbers.
Example:
If we'd want to find all the primes under n we would:
- Start at two and cross out every multiple of 2: 4, 6, 8... up to n.
- Find the next number that hasn't been crossed out and mark it as prime: 3.
- Cross out all of multiples of this number: 3, 6, 9... up to n.
- Find the next number not crossed out: 7.
- Repeat.
Graphics
Learning about rendering to the screen was one of the main goals of this project. After some research I decided that SDL2 was the way forward. With some help form teh amazing articles at Lazy Foo I created a wrapper around the framework allowing me to render to the screen.
The Visualisation.
To visualise the algorithm in an artistic manner I decided to plot every number in a spiral as a series of dots, starting at the number 2 and spiralling outwards. Every dot has a hue according to it's place on the HSV colour wheel. The saturation of each dot is determined by how many times it has been passed by the sieving algorithm, essentially signalling it's "un-primeness". To achieve this, the program actually iterates every number it encounters, even ones having been marked before, and renders the spiral every step. To visualise the prime numbers, the hue is rotated by 180 degrees to the colour composite of the area and the saturation increased to the maximum. Keyboard controls allow the user to pause and restart the animation and altering the step-size for the hue, and the number of degrees between dots.