2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89, and 97.

Prime numbers have attracted a lot of attention throughout mathematical history. As long ago as 250 B.C.E., Eratosthenes gave a method for determining all the primes less than a given limit, now known as the sieve of Eratosthenes. Write down the numbers down from 2 up to

*n*. Circle the number 2. Now cross off every second number after 2: 4, 6, 8, etc. Look for the smallest uncrossed-off, uncircled number. It is 3. Circle it, and cross off every thrid number after 3: 6 (which was crossed off earlier), 9, 12, etc. Now again look for the smallest uncrossed-off, uncircled number. It is 5. Continuing in this fashion, we get a list of all the primes up to

*n*.

In recent years, there has been lot of progress in understanding the primes. For example, in 2002, Agrawal, Kayal, and Saxena found a very efficient method of determining whether a number is a prime. It runs in polynomial time; that is, the number of steps to determine if a number

*n*is prime is bounded by a polynomial in the number of digits of

*n*. And just this year (correcting two previous versions that were incorrect), Goldston, Motohashi, Pintz, and Yildririm proved that the smallest possible gap between a prime

*p*and the next-larger prime grows more slowly than log

*p*. This is a small step towards proving the "twin prime conjecture", which says that there are infinitely many primes

*p*such that

*p*+2 is also prime.

Despite this progress, many open problems about the primes remain. For example, while it is known that there are infinitely many prime numbers, no one knows if there are infinitely many primes of the form 2

^{p}- 1. These are called Mersenne primes, after the 17th century French priest who studied these primes (and made some incorrect claims about them.) Mersenne primes are interesting because they are particularly easy to test for primality, and because of their relationship to an historical problem in number theory, the perfect number problem.

A positive integer is perfect if the sum of its divisors is equal to twice the number. For example, the divisors of 6 are 1, 2, 3, and 6, and they sum to 12, which is twice 6. No one knows currently if there are infinitely many perfect numbers, but Euclid (around 300 B.C.E.) noted that if 2

^{p}- 1 is a prime number, then (2

^{p}- 1)2

^{p-1}is perfect, and Euler proved that

*all*even perfect numbers are of this form. No odd perfect numbers are known, but there is still no proof that none exists.

Now a new Mersenne prime has been found: 2

^{30402457}-1. This immense number of 9,152,052 digits was discovered by Curtis Cooper and Steven Boone at Central Missouri State. This is the largest known prime number and the 43rd known Mersenne prime.

To get some idea of the recent progress in finding Mersenne primes, when my book

*Algorithmic Number Theory*was published in 1996, we included a table of the largest primes known throughout history. We stopped with 2

^{859433}-1, the 33rd Mersenne prime. Since then, 10 new Mersenne primes have been found! What accounts for this progress?

Largely, it is distributed computing. The GIMPS project ("Great Internet Mersenne Prime Search") coordinates factorization efforts by thousands of computers worldwide. While there are millions of computers, few are actually doing anything useful at any given time. The genius of GIMPS is to harness these unused cycles to find new large primes.

I'm often asked, what is it good for? The answer is -- like a painting by da Vinci -- nothing, really. It adds to our knowledge about Mersenne primes, but it probably will never lead to a proof that infinitely many Mersenne primes exist. Nor does knowing large Mersenne primes contribute to cryptography. But -- again like the da Vinci painting -- the subtle mysteries of the primes have a worldwide and longstanding appeal.