# How many prime numbers are there?

One of the first questions you can ask about prime numbers is simply this: how many are there? Are there only finitely many, or are there infinitely many primes?

This question arises naturally from the empirical observation that primes seem to get rarer as you search through more and more numbers. Forty percent of the integers less than 10 are prime, but only 25 percent of the integers less than 100, and only 16.8 percent of the integers less than 1000. So, the question really asks if the primes eventually get so rare that there are no more of them.

Suppose for the moment that there really are infinitely many primes. It is immediately clear that we cannot write them all down explicitly, since such a task would (literally) take forever. To prove that there are infinitely many primes, we would either have to write down a general formula that could be used to produce infinitely many different primes, or else we would have to proceed by a more indirect method.

On the other hand, suppose there are only finitely many primes. Then there must be a biggest prime. How could you find it? On a related note, suppose that the largest prime you ever cared about was less than some (presumably enormous) integer N. How can you list all prime numbers less than N?

Suppose someone gives us a finite list of prime numbers, say

$P$1, P2, ..., PM.

Is this list complete? Or, is there, somewhere in the universe, a prime number that is not in the list?

To understand fully this latest question, you need to realize that it is a reformulation of the basic question about the number of primes. If there are only finitely many, then we should be able to list them all. If there are infinitely many, then any finite list must be inadequate---in the very precise sense that some prime exists that is not on the list.

Now we have two choices:

• If we believe there are only finitely many primes, then we should look for a method to find the largest prime. A natural next step would be to try to list all the primes.
• If we believe there are infinitely many primes, then we should try to prove this result by contradiction. That is, we should start with a list of primes, which purports to be complete, and somehow use the list to produce another prime.

So, it's time for you to make a decision. Think about the problem for a while, and then decide: Are there finitely many or infinitely many prime numbers?

Disclaimer: This page was last updated on 12 October 2002. It is entirely possible that the information contained herein no longer has any connection with reality (assuming it ever did). Feel free to send constructive comments or inane criticisms to:
Kevin R. Coombes
Department of Biostatistics
University of Texas M.D.Anderson Cancer Center
1515 Holcombe Blvd., Box 447
Houston, TX 77030