Prime Time

sieve:  a utensil with meshes or holes to separate finer particles from coarser ones or solids from liquids. – Merriam Webster Dictionary

Every student who has completed grade school learned about prime numbers.  We learned what they are:  natural numbers greater than 1 with factors of only 1 and themselves.  We learned methods to find them.  We learned to use them in factoring.  An elementary exposure was part of the ticket out of elementary mathematics.

Not everyone, though, was exposed to the Sieve of Eratosthenes.  The Sieve is an ancient method (circa 240 B.C.) that gives us a systematic way to find primes, starting with 2.  You write the natural numbers from 1 up to however high you want to go.  You cross 1 out, as it is neither prime nor composite.  Start with 2, your first prime.  (I usually have students circle it.)  Then, cross out all multiples of 2, as they have additional factors other than 1 and themselves.  Go back, and the next available number, 3, is prime.  Circle it.  Cross out all multiples of 3.  Go back, and the next available number, 5, is prime.  Circle it.  Cross out all multiples of 5.  Go back.  Repeat over and over until you reach the end of your sieve.

The method is pretty simple in its execution, but it’s time-consuming when trying to sort out primes for large numbers.  Even with today’s super computers, the method takes up too much memory and time.  But, there’s hope!  Peruvian mathematician Harald Helfgott has found a way to modify the sieve so that computers don’t need to use as much memory space.  Scientific American published an article on the discovery, and it is worth a read.

New Take on an Ancient Method Improves Way to Find Prime Numbers


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s