A prime number is a number that has just two factors (divisors): itself and the number 1. For example, 7 is prime, since its only divisors are 7 and 1. The number 6 is not prime, since it is divisible by 2 and 3. Numbers that have more than two divisors are called composite numbers.

Prime numbers have fascinated mathematicians since the age of Pythagoras. By Euclid's time, mathematicians knew the fundamental theorem of arithmetic: every whole number can be written as the product of prime numbers, in a unique way (up to reordering of the factors). For example, 60 can be written as 2 x 2 x 3 x 5. Thus, prime numbers can be looked upon as the building blocks for the whole numbers.

Among small numbers, many are prime: 2, 3, 5, 7, 11, 13 and so forth. Among larger numbers, however, the number of primes thins out greatly, raising an important question for the ancients: is there a finite or...