Suppose there are finitely many primes, say , and consider . Then , otherwise would divide . Likewise none of divide . So either is itself prime, or it has a prime factor outside the list ; either case contradicts the assumption that the list contained all primes.

Let be all the primes. Since any number is uniquely expressed as a product of primes, consider numbers of the form with ; each can be rewritten as

where for all , and is some integer.

Given , a number less than or equal to of this form has , so there are at most such numbers. If , that is , some number less than or equal to is not of this form, and it must have a prime factor outside the list — a contradiction.

Euclid’s proof bounds the th prime by , while this argument gives . In fact the th prime is approximately for large : the prime number theorem.