#### Problem 74E

A prime number is a positive integer that has no factors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17,… We denote by (n) the number of primes that are less than or equal to n. For instance, (15)=6 because there are six primes smaller than 15. a Calculate the numbers (25) and 100. Hint: To find 100, first compile a list of the primes up to 100 using the sieve of Eratosthenes: Write the numbers from 2 to 100 and cross out all multiples of 2. Then cross out all multiples of 3. The next remaining number is 5, so cross out all remaining multiples of it, and so on. b By inspecting tables of prime numbers and tables of logarithms, the great mathematician K. F. Gauss made the guess in 1792 when he was 15 that the number of primes up to n is approximately n/In n when n is large. More precisely, he conjectured that limn(n)n/Inn=1 This was finally proved, a hundred years later, by Jacques Hadamard and Charles de la Valle Poussin and is called the Prime Number Theorem. Provide evidence for the truth of this theorem by computing the ratio of (n) to n/In n for n=100, 1000, 104, 105, 106, and 107. Use the following data:(1000)=168(104)=1229,(105)=9592,(106)=78,498,(107)=664,579. c Use the Prime Number Theorem to estimate the number of primes up to a billion.