366 ARITHMETIC 4.5.4 can be (Virtual web hosting) set up by
366 ARITHMETIC 4.5.4 can be set up by means of a short auxiliary program, which builds the table just after the factoring program has been loaded into the computer; see Algorithm 1.3.2P, or see exercise 8. How many trial divisions are necessary in Algorithm A? Let T(Z) be the number of primes 5 Z, so that 7r(2) = 1, ~(10) = 4; the asymptotic behavior of this function has been studied extensively by many of the world s greatest mathematicians, beginning with Legendre in 1798. Numerous advances made during the nineteenth century culminated in 1899, when Charles de la Vall6e Poussin proved that, for some A > 0, 7(x)= s21 & + o(xe-A@=). [A&m. Cowon&% Acad. Roy. Belgique 59 (1899), l-74.1 Integrating by parts yields T(x)=j& + (In:) + ($)3 + . . . + (l,;):+l + o( (log g+J C4) for all fixed r 2 0. The error term in (3) has subsequently been improved; for example, it can be replaced by 0(x exp(-A(log x)3/5/(log log x)1/5)). [See A. Walfisz, Weyl sche Exponentialsummen in der neueren Zahlentheorie (Berlin, 1963), Chapter 5.1 Bernhard Riemann conjectured in 1859 that T(X) = c p(k)L($q/k + O(1) = L(z) -&(&) -;qs) +. *. (5) k>l where L(s) = sr dt/lnt, and his formula agrees well with actual counts when z is of reasonable size. For example, we have the following table: X n(x) x/in x L(x) Riemann s formula 103 168 144.8 176.6 168.36 106 78498 72382.4 78626.5 78527.40 109 50847534 48254942.4 50849233.9 50847455.43 However, the distribution of large primes is not that simple, and Riemann s con- jecture (5) was disproved by J. E. Littlewood in 1914; see Hardy and Littlewood, Acta Math. 41 (1918), 119-196, where it is shown that there is a positive con- stant C such that T(Z) > L(x) + Cfilogloglog x/log x for infinitely many x. Littlewood s result shows that prime numbers are inherently somewhat mys- terious, and it will be necessary to develop deep properties of mathematics before their distribution is really understood. Riemann made another much more plausible conjecture, the famous Riemann hypothesis, which states that the complex function c(z) is zero only when the real part of z is equal to 4, except in the trivial cases where z is a negative even integer. This hypothesis, if true,