Prime numbers were first studied extensively by ancient Greek mathematicians. The Pythagorean school (500 BC to 300 BC) where interested in the numerological properties. By Euclid's time (300 BC), several important results about primes had been proved. Euclid went on to prove that there are an infinite number of prime numbers. This proof is the first known one using the method of reduction to absurd. Euclid also proved the Fundamental Theorem of Arithmetic: Every integer can be written as a product of primes in an essentially unique way. In 200 BC, Eratosthanes devised an algorithm for calculating primes called the Sieve of Eratosthanes.

There is a great gap in the history of prime numbers during the Dark Ages.

The next major development was made by Fermat in the 17th Century. Fermat proved a speculation of Albert Girard that every prime of the form 4n + 1 can be written in a unique way as the sum of two squares, and any number could be written as the sum of four squares. In his corespondance with Mersenne, Fermat conjectured that 2n + 1 was always prime if n was a power of 2. He had verified this for n = 1, 2, 4, 8, and 16 but was did not know 232+1 was prime or not. 100 years later Euler showed that 232 + 1 was 4294967297 and is divisible by 641, hence not prime.

The next major step in prime number theory came from a monk named Mersenne. Mersenne studied many numbers of the form 2n - 1 and a class of numbers named Mersenne numbers were named after him. These numbers attracted attention because it was easy to show that unless n was prime the number must be composite. Not all of these numbers are prime, though for many years (and again today) they provided the largest prime numbers. For 200 years M19 was the largest known prime until Euler proved that M31 is prime. This established the record for another 100 years until M127 is prime until the age of the computer. In 1952 the Mersenne numbers M521, M607, M1279, M2203 and M2281 were proved to be prime with the aid of a computer.

Euler's work extended that of Fermat's working with amicable numbers and stated what is known today as the Law of Quadratic Reciprocity. Euler also worked with sequences of primes and divergent series.
1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...
is a divergent series, though even the most powerful computers today can only sum it to about 4.

Gauss studied the density of prime numbers along the integers. In the first 100 integers there are 9 primes, while the next 100 only has 2. Gauss showed that on a large scale, the distribution is very regular. Gauss once told a friend that whenever he had a spare 15 minutes he would spend it counting numbers in a 'chiliad' (a rage of 1000 numbers). It was estimated that by the end of his life he had counted all the primes up to about 3 million.

Today the counting of prime numbers continues, the most well known is GIMPS, The Great Internet Mersenne Prime Search.