Do primes become more or less frequent as you go further out on the number line? That is, are there more or fewer primes between $1$ and $1{,}000{,}000$ than between $1{,}000{,}000$ and $2{,}000{,}000$?

A proof or pointer to a proof would be appreciated.

  • 4
    $\begingroup$ Yes (as has been answered): the heuristic reason is that we can list the primes $p_1, p_2, \dots$. Each time you apply the sieve of Eratosnese you exclude the numbers divisible by $p_n$ and weed out "$(1-1/p_n)$" of the natural numbers (i.e., asymptotic density). So in the end you are left with $\prod ( 1 - 1/p_n)$ fraction of the natural numbers; since the sum $\sum \frac{1}{p_n} = \infty$, this is the proportion zero. So we should expect the primes to have density zero. $\endgroup$ Jul 21 '10 at 0:23
  • 2
    $\begingroup$ Check out the Riemann-zeta function if you want something a bit more technical. It gives a pretty precise estimate of the distribution of primes, indirectly. $\endgroup$
    – Noldorin
    Jul 21 '10 at 7:38

From the Wikipedia article about the prime number theorem:

Roughly speaking, the prime number theorem states that if a random number nearby some large number N is selected, the chance of it being prime is about 1 / ln(N), where ln(N) denotes the natural logarithm of N. For example, near N = 10,000, about one in nine numbers is prime, whereas near N = 1,000,000,000, only one in every 21 numbers is prime. In other words, the average gap between prime numbers near N is roughly ln(N).


The Sieve of Eratosthenes is a very intuitive visual representation of why the frequency of prime numbers goes down as you go further out on the number line.

  • $\begingroup$ This is really a less detailed version of Akhil's comment. $\endgroup$
    – BBischof
    Jul 21 '10 at 4:43
  • 3
    $\begingroup$ @BBischof Akhil's comment derives the answer to this question with mathematical rigor. My answer offers a link to a visual representation of the trend for the sake of gaining intuition. Its nice to have both the proof of the result and intuition about the result. $\endgroup$
    – Ami
    Jul 21 '10 at 5:01
  • $\begingroup$ Agreed @Ami, it is a useful answer if not as rigorous. $\endgroup$
    – dsolimano
    Jul 21 '10 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.