Fun with Prime NumbersWe often hear the word prime used to describe something that is first-rate, or superior in some way. This remains to be true when we speak of the set of numbers that are designated as prime as well. We define the prime number system to be the set of numbers which have only two divisors (from the natural numbers): one, and the number in question. Composite numbers, in contrast, must include at least one additional natural number that divides the value in question.

Examples of prime numbers would be 2, 5, 29, and 97; these values have no other factors (aka divisors) besides one and themselves. Two is the only even prime number, for obvious reasons (every other even value is divisible by 2!). Some samples of composite numbers include 16, 125, 333, and 2401, which, each have at least one additional divisor besides one and the specimen considered.

Eratosthenes’ Sieve

Since very early on, primes have been recognized as special, and as early as 200 BC, efficient methods have been available which can determine these. Eratosthenes developed a “sieve” which allows easy elimination of all composite numbers, leaving only the primes behind. This algorithm is beautiful in its simplicity:

- Begin with a list of numbers which you wish to examine and categorize as either prime or composite. Eliminate the number 1 as it is neither prime nor composite.
- The next value, 2, is the first prime number. Go through your list, crossing off every multiple of 2 (which equates to crossing off every second number).
- Look for the next value that is not crossed off, 3, and repeat the process with the multiples of 3 (some of these will have already been crossed off by the earlier process on the number 2 – that’s OK!).
- Repeat this process (in order!) for all remaining values that have not been previously eliminated, up to the square root of the largest value in your list. After you have reached this value, you will not reduce your list any further; what remains are the prime numbers less than your maximum value.
Click here for a PowerPoint illustration of the Sieve of Eratosthenes!

Another Type of Sieve

An interesting phenomenon can also be observed when looking at the graph of the function . We can see that this simple graph, a common parabola, can serve as a sieve of sorts when trying to find the set of numbers designated to be prime. In fact, if one understands Eratosthenes’ sieve, one will see that this is merely a geometric interpretation of the same process.

Consider the set of points on this graph, where the x-value of the coordinate is some integer with an absolute value greater than 1. Now, we will connect these points which are situated on the left side of the graph with those that are situated on the right side of the graph. We find that the slope of these segments can be represented as while the y-intercepts can be represented as The implication of this is that as far as these segments are drawn, they will pass through all possible composite values as y-intercepts; only prime numbers will escape their intrusion.

The Algebra behind the Algorithm

Let a coordinate on the left hand side of the graph be represented as ( and

Let a coordinate on the right hand side of the graph be represented as (

Then the point-slope form of this equation can be written as:

But the numerator can be factored and expressed as:

Which of course can simplify to be written as:

Distributing the right hand side yields:

Now collecting our like terms, we have:

And our final manipulation into slope-intercept form is:

Showing our slope to indeed beand our y-intercept to be . Remember, that since our is on the left hand side of the graph, it represents a negative value, so the product actually represents a positive value.

Click here to see a Geometer’s Sketchpad illustration of this occurrence. Click through each step sequentially and you may find this to be an interesting visual relating to those superlative values, the prime numbers.

Sieve and let Sieve

So we see the beauty of the archaic algorithm is mimicked graphically by this quadratic sieve, and the elegance is quite breathtaking! The prime numbers have the starring role in both of these fun and fascinating phenomena. What other prime number sieves exist? Are they as lovely as the ones explored in this writing?

Sources:

http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Eratosthenes.html

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

http://www.mathteacherctk.com/blog/2011/10/the-parabolic-sieve-of-prime-numbers/

http://www.3villagecsd.k12.ny.us/wmhs/Departments/Math/OBrien/eros2.html