This project is a simple visual quadratic sieve for catching primes. It's made with Processing, a language and IDE built on Java designed to make it easier to code and draw with code.
This project gives a visual way to generate primes by sieving out all composite numbers up to a given number (represented in this visualization by the highest integer on the y-axis times two). This leaves us with primes. Composites are blue, and primes are green.
- We start by drawing the parabola
.
- Then, we connect each integer point on one branch (above or below the x-axis, starting with
, since we don't care about multiples of one for finding composites) of the parabola to each integer point on the opposite branch (and vice versa).
Notice that just as the line between the points on the parabola where
and
intersects the
-axis at
, the line between the points on the parabola where
intersects the x-axis at
(find a nice visual explanation of why this is here).
- The parabola
- When we find a new intersection like this, we mark the point on the x-axis blue and stop checking it since we know it's composite.
- When our current maximum y-value exceeds anything that could be a factor of a given x (defined for this visualization as anything greater than
), we mark it green and can be certain that it's prime.
This visual sieve was invented by Russian mathemeticians Yuri Matiyasevich and Boris Stechkin.
- A visual explanation of why we cross the points we do (and more about this sieve)
- A brief explanation of quadratic sieves, including the visual sieve
To run this visualization, download and execute the jarfile associated with the most recent release (see the releases page). Read the notes for the version; you might need to install a JDK.
If you would rather run the visualization in Processing, download Processing and the source code associated with the most recent release (see the releases page). Extract the source code and open a .pde file in the resulting folder to open the Sketch. Then, press the play icon to run.