(Click here for a Postscript version of this page.)
It is known since Euclid that there exists an infinite number of primes. A very large number of proofs can be found in the litteratures (this is certainly one of the mathematical result with so many proofs).
The way this infinity behaves is a great mathematical question. More precisely, mathematicians defined the function p(x) by the number of prime numbers less or equal than a given value x :

One of the mathematical breakthrough of the nineteenth century has been the prime number theorem, proven independantly by Hadamard and De La Vallée Poussin in 1896. Roughly speaking, it states that as x becomes big, p(x) is close to x/log(x) (in other words, a random number x has a "probability" 1/log(x) to be prime).
More precisely, the prime number theorem states that



More information on the prime number theorem will be soon available on this site.
Studing the distribution of primes can be done by sieving numbers. In the ancient times, Eratosthenes described a sieve which permits to compute the prime number less than a given value x. Considering the list of integers from 2 to x, it consists by eliminating from this list the non trivial multiples of the primes less than Öx. The non eliminated values are the prime numbers less than x. This sieve is now classical and was extensively used for example as a distributed projet on the net to compute all prime numbers less than 10^{16} (see Rensselaer's Twin Primes Computing Effort where a sieve has been used to study twin primes).
Sieves can be used to study statistical data on prime numbers, like counting the number of primes, looking for small and large gaps between consecutive primes, counting the number of twin primes (primes p for which p+2 is also a prime), counting primes with a given form, etc.
The cost of classical sieves are close to linear. For example, the use of the classical Sieve of Eratosthenes to compute p(x) can be done in time O(xloglog(x)). More efficient sieve versions are a little quicker, but the asymptotic cost remains close to linear. A two years distributed computation was necessary for example, to compute a certain family of primes less than 10^{16} with sieving techniques.
Legendre was the first to suggest a method to compute p(x) without locating all the primes less than x. However, his method was not of immediate utility. The first real breakthrough in the p(x) computation was done by Meissel in 1871, who computed p(10^{8}) and later p(10^{9}) in 1886, which was a value far beyond the known tables of primes at that time. In 1959, D. H. Lehmer simplified Meissel's method to compute p(10^{10}) using an IBM 701. Bohmann in 1972 computed p(10^{13}). Notice that the old calculations p(10^{9}), p(10^{10}) and p(10^{13}) turned out to have slight errors, and the later computations were systematically verified by a second computation with different parameters. In 1985, Lagarias, Miller and Odlyzko improved again Meissel method and obtain an algorithm running in time O(x^{2/3}/log(x)) and memory O(x^{1/3}log^{2}(x)) (see [3]). They obtained the value p(4 ×10^{16}). In 1994 Deléglise and Rivat improved the technique once again [2] and saved a factor log(x) in the time cost (but they lost the same factor on the memory cost). They found higher values : p(10^{17}), p(10^{18}) and later, the values p(10^{19}) and p(10^{20}) with a more efficient implementation by Deléglise.
Recently, Xavier Gourdon (one of the two authors web site) made technical improvement to the Meissel, Lagarias, Miller, Odlyzko, Deléglise and Rivat algorithm (see Computation of pi(x) : improvements to the Meissel, Lehmer, Lagarias, Miller, Odlyzko, Deléglise and Rivat method). As a result, some constant factors have been saved and memory usage is lower (no precise asymptotic study has been made until now). The improvement also permits to distribute a large p(x) computation on several machines with a very low memory exchange (Lagarias, Miller and Odlyzko already considered the problem of distributing the computation in [3] but subsequent memory exchange was needed between the machines), provided a precomputation of cost O(x^{1/2}) is made (a description of the improvements will soon be available on this site). The implementation is a program which permitted to obtain a new p(x) record computation in 2000. The value of

The prime number theorem states that p(x) is close to the function


The known values of p(x) today agree with this estimate (see the table below), and even agree with a more tight estimate. It is in fact not so easy to have an idea of what should be exactly the error term. At the end of the 1930's, Cramer proposed a model [4] to construct conjectures on distribution of prime numbers. The Cramer model suggest that the prime numbers behave like a random sequence with the same growth constraint (in other words, each number n have a probability 1/log(n) to be prime in this model). According to this model, the number of primes almost should almost surely (with probability 1) satisfy the equality


A result of Littewood show that the function q(x) satisfies

Riemann and Gauss believed that Li(x) > p(x) (which is equivalent to q(x) < 0) for every x > 3, and all the computed values of p(x) today satisfy this inequality. However it has been proved by Littlewood in 1914 that q(x) changes its sign infinitely often. In 1933, S. Skewes established that the first change of sign occurs before the impressive number 10^{k} with k = 10^{1034}. This bound has been improved in 1966 by R.S. Lehman who gave the bound 10^{1166}. Later in 1985, H. Te Riele proved that the first change of sign occurs before x = 6.69 ×10^{370}. The best bound known so far has been obtained in 2000 by Carter Bays and Richard H. Hudson [1] who proved that the first change of sign occurs before x = 1.39822 ×10^{316}. Of course, such a large value is not reachable today, but the function q(x) have large variations in the last table values, suggesting that a change of sign could occur not too far from this zone. The p(x) project could afford the first known value x for which p(x) > Li(x) ! Finding the first change of sign if even more difficult !
Using a program written by Xavier Gourdon, Patrick Demichel computed a large number of values of Li(x)p(x) for x between x = 10^{15} and x = 7×10^{15} every 10^{12}. As a result, he obtained a graphic view of this function in this range. As expected, the resulting plotted function is very chaotic.
This table of values of p(x) contains the difference with the function Li(x) (third column), the value of the "normalized" Cramer function

Remember that the Cramer model implies the conjecture 1 £ q(x) £ 1, which is a stronger conjecture than the bound obtained from the Riemann Hypothesis, and that a change of sign of q(x) has not been found yet (see the section Oscillations above).
Note : the following page contains the description of an interesting algorithm to compute the parity of p(x) in time O(Öx log(x)), together with a table of the parity of p(x) for some values of x (this page contains errors in the parity of p(x) for some values of x ³ 5×10^{19}; an implementation of the corresponding algorithm was made by Xavier Gourdon and the parities found confirm the values of our table).
A more complete set of values of p(x) is available in our pi(x) table page.
x  p(x)  Li(x)p(x)  q(x)  Comments 
10^{6}  78,498  129  0.209  
10^{7}  664,579  336  0.1809  
10^{8}  5,761,455  753  0.1339  Meissel 1871 
10^{9}  50,847,534  1,700  0.0994  Meissel 1886 (Corrected) 
10^{10}  455,052,511  3,103  0.0594  Lehmer 1959 (Corrected) 
10^{11}  4,118,054,813  11,587  0.0725  
10^{12}  37,607,912,018  38,262  0.0781  
10^{13}  346,065,536,839  108,970  0.0723  Bohmann 1972 (Corrected) 
10^{14}  3,204,941,750,802  314,889  0.0678  Lagarias Miller Odlyzko 1985 
10^{15}  29,844,570,422,669  1,052,618  0.0735  LMO 1985 
10^{16}  279,238,341,033,925  3,214,631  0.0726  LMO 1985 
10^{17}  2,623,557,157,654,233  7,956,588  0.0581  Deléglise Rivat 1994 
10^{18}  24,739,954,287,740,860  21,949,554  0.05177  Deléglise Rivat 1994 
10^{19}  234,057,667,276,344,607  99,877,774  0.0760  Deléglise 1996 
10^{20}  2,220,819,602,560,918,840  222,744,643  0.0546  Deléglise 1996 
2*10^{20}  4,374,267,703,076,959,271  472,270,046  0.0823  X. Gourdon 2000 Nov 
10^{21}  21,127,269,486,018,731,928  597,394,253  0.0471  X. Gourdon 2000 Nov 
2*10^{21}  41,644,391,885,053,857,293  1,454,564,714  0.0816  pi(x) project, 2000 Dec 
4*10^{21}  82,103,246,362,658,124,007  1,200,472,717  0.0479  pi(x) project, 2000 Dec 
10^{22}  201,467,286,689,315,906,290  1,932,355,207  0.0491  pi(x) project, 2000 Dec 
1.5*10^{22}  299,751,248,358,699,805,270  2,848,114,312  0.0592  P. Demichel, X. Gourdon, 2001 Feb 
2*10^{22}  397,382,840,070,993,192,736  2,732,289,619  0.0493  pi(x) project, 2001 Feb 
4*10^{22}  783,964,159,847,056,303,858 (*)  5,101,648,384  0.0655  pi(x) project, 2001 Mar (Current world record) 
(*) Thanks to Leonid Durman who detected that I had written the value of li(4*10^{22}) instead of p(4*10^{22}). The mistake have been corrected.
Thomas Nicely site about twin primes, primes gap, etc. The pages also contain values of pi(x) for x up to 3.10^{15} every 10^{12}.
Henri Lifchitz page about an interesting algorithm to compute the parity of p(x) in time O(x^{1/2} log(x)).
numbers, constants and computation