Primes -- A brief introduction
The List of Largest Known Primes
The Largest Known Primes Icon
  An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself.  For example, the prime divisors of 10 are 2 and 5; and the first six primes are 2, 3, 5, 7, 11 and 13 (the first 10,000, and other lists are available).  The Fundamental Theorem of Arithmetic shows that the primes are the building blocks of the positive integers: every positive integer is a product of prime numbers in one and only one way, except for the order of the factors.

The uses of primes are manifold.  They were first studied because many of the properties of numbers are directly tied to their factorizations.  Beside their austere intrinsic beauty, prime numbers are now key to the Internet revolution because they are used for a variety of encryption methods used to keep transactions safe.  NASA scientists even decided that they are a good sign of intelligence and have included a short list of primes on the plaques sent out with the voyager spacecraft.  This interest is not new.  Over 200 years ago, Carl Friedrich Gauss (one of the greatest mathematicians of all time) wrote:

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated. (Carl Friedrich Gauss, Disquisitiones Arithmeticae, 1801)
The ancient Greeks proved (ca 300 BC) that there were infinitely many primes and that they were irregularly spaced (there can be arbitrarily large gaps between successive primes).  On the other hand, in the nineteenth century it was shown that the number of primes less than or equal to n approaches n/log n) (as n gets very large); so a rough estimate for the nth prime is n log n (see the document "How many primes are there?")

The Sieve of Eratosthenes is still the one of the most efficient way of finding all very small primes (e.g., those less than say 1,000,000,000,000).  However, most of the largest primes are found using special cases of Lagrange's Theorem from group theory.  See the separate documents on proving primality for more information.

In 1984 Samuel Yates defined a titanic prime to be any prime with at least 1,000 digits [Yates85].  When he introduced this term there were only 110 such primes known; now there are over 1000 times that many!  And as computers and cryptology continually give new emphasis to search for ever larger primes, this number will continue to grow.  Before long we expect to see the first ten million digit prime.

There is so much more to be said!  Why not spend a few moments perusing this site or spend a quiet evening with one of the excellent texts in our reference pages.