# Percentage of primes among the natural numbers

How high is the percentage of primes in $\mathbb{N}$?

($\mathbb{N} := \lbrace { 1, 2, 3, \ldots \rbrace }$ ; a prime is only divisible by itself and 1 in $\mathbb{N}$)

The percentage has to be lower than 50% as all even numbers (except for 2) aren't primes. So the percentage has to be lower than $1 - (\frac{1}{2} + (\frac{1}{3} - \frac{1}{6})) = 1 - (\frac{1}{2} + \frac{1}{6}) = 1 - (\frac{1}{2} + \frac{1}{2 \cdot 3}) = \frac{1}{3}$

I guess it will be something like that:

$$\frac{\text{primes in } \mathbb{N}}{\text{numbers in } \mathbb{N}} = 1 - \sum_{i=\text{first Prime}}^\text{primes} \frac{1}{\prod_{j=\text{first prime}}^{i\text{-th prime}} j}$$

But calculating this (exact) value goes definitely beyond my math skills. Can somebody help me?

• google "prime number theorem". And, it is, indeed, deep. Nov 14, 2011 at 18:41
• @David In fact, the weaker result of Chebyshev that $c \frac{x}{\log x} \leqslant \pi(x) \leqslant C \frac{x}{\log x}$ (for constants $0 < c < C < \infty$) already tells that the primes have zero natural density among $\mathbb N$. This result is, of course, very non-trivial, but not too deep; I think the sieve methods are good enough to get it. I don't think that the OP is asking about the precise asymptotics of the density... Nov 14, 2011 at 18:44
• The fact that $\lim_{n \to \infty} \dfrac{\text{primes } \leq n}{n} = 0$ is much easier to derive than the prime number theorem, or even Chebyshev's estimates. The OP is on the right track with his computions for sieving out $2$ and $3$. Nov 14, 2011 at 19:07
• @moose: Your estimate, which I interpret as $1-\left(\frac{1}{2}+\frac{1}{6}+\frac{1}{30}+\frac{1}{210}+\cdots\right)$ gives a positive density, which is not right. Maybe observe that the fraction taken care of by $2$, $3$, and $5$ is actually $(1-1/2)(1-1/3)(1-1/5)$, which is $11/15$, while your $1/2+1/6+1/30$ is $21/30$. Nov 14, 2011 at 19:07
• @moose: I am not sure that there is some consensus about how long to wait before accepting an answer (see meta.math.stackexchange.com/questions/2553/…), but I think that you've accepted to soon. The answer by Pete Clark is beautiful and the proof he suggests is really elementary (at least in comparison with the proofs suggested in other answers so far). Nov 14, 2011 at 19:51

People are quoting the Prime Number Theorem here, but that is pretty serious overkill. Even Chebyshev's theorem is a level above, in my opinion.

In my undergraduate number theory course, I prove that the prime numbers have density zero in the positive integers (including a careful statement of what this means). The proof is given as Theorem 6 in these notes (Wayback Machine). In fact it builds on the OP's observation that the density must be at most $$\frac{1}{2}$$ because half of all numbers are divisible by $$2$$. Similarly the density must be at most $$\frac{1}{3}$$ because every prime number $$p > 5$$ is relatively prime to $$6$$, and $$\frac{\varphi(6)}{6} = \frac{1}{3}$$. One can get a complete proof by showing that for each $$\epsilon > 0$$, there exists a positive integer $$d$$ such that $$\frac{\varphi(d)}{d} < \epsilon$$. This was proved earlier in the course: it is Proposition 6 in this set of notes (Wayback Machine). The proof doesn't use any analytic fact deeper than the divergence of the harmonic series.

• A little note: This approach gives an upper bound of $O(\frac{x}{\log \log x})$ on the number of primes not exceeding $x$ (as mentioned in the linked notes after Theorem 6 :)). Nov 14, 2011 at 19:41
• Dear Pete, I agree that this is the natural proof of the density statement that the OP is asking about. Regards, Nov 14, 2011 at 20:39

I will denote the set of all primes by $$\mathbb P$$.

It is not exactly clear what one can understand under percentage of primes, but one possible interpretation is the limit $$\lim\limits_{n\to\infty} \frac{\pi(n)}n = \lim\limits_{n\to\infty} \frac{|\{p\in\mathbb P; p\le n\}|}n$$ of the ratio of primes and all numbers in the interval $$[1,n]$$. This is precisely the asymptotic density of the set $$\mathbb P$$ and using Prime number theorem one can show that it is equal to zero.

The asymptotic density of the set $$A$$ is defined as $$d(A)=\lim\limits_{n\to\infty} \frac{|\{a\in A; a\le n\}|}n.$$ A possible way to show $$d(\mathbb P)=0$$ without using PNT is to use the result from the paper Ivan Niven. The asymptotic density of sequences. Bull. Amer. Math. Soc., 57(6):420-434, 1951.

Corollary 1. If for a set of primes $$\{p_i\}$$ we have $$d(A_{p_i})=0$$ for every $$i$$, and if $$\sum p_i^{-1}=\infty$$ then $$d(A)=0$$.

Here, for any $$A\subseteq\mathbb N$$ and a prime $$p$$, the set $$A_p$$ is defined as $$A_p=\{n\in A; p\mid n, p^2\nmid n\}.$$

Applying the above result with $$A=\mathbb P$$ and $$\{p_i\}=\mathbb P$$ gives $$d(\mathbb P)=0$$.

We are using the fact that $$\sum_{p\in\mathbb P} \frac1p=\infty$$. A very nice proof of this fact was given by Erdős, see Proofs from The Book by Martin Aigner, Günter M. Ziegler p.5.

Another short proof of $$d(\mathbb P)=0$$ is given in this paper:

S. E. Mamangakis. Shorter notes: Remark on $$\pi(x) = o(x)$$. Proc. Amer. Math. Soc., 13(4):664--665, 1962

According to the Prime Number Theorem $$\lim_{n\to\infty}\frac{\pi(n)}{n/\log(n)}=1\tag{1}$$ where $$\pi(n)$$ is the number of primes less than or equal to $$n$$. Therefore, there is an $$N$$ so that if $$n\ge N$$, $$\frac{\pi(n)}{n}\le\frac{2}{\log(n)}\tag{2}$$ Since there are infinitely many primes and infinitely many positive integers, there is no way to divide the number of primes by the number of positive integers to get a proportion. The next best attempt at a proportion would be the limit of the proportion in $$[1,n]$$: $$\lim_{n\to\infty}\frac{\pi(n)}{n}\tag{3}$$ Inequality $$(2)$$ says that the limit in $$(3)$$ is $$0$$.

Pete Clark mentions that the Prime Number Theorem is overkill for this question, and I agree. In light of this, let's consider first the density of positive integers not divisible by a particular prime $$p$$. Define $$F_p=\{n\in\mathbb{Z}^+:p\nmid n\}\tag{4}$$ It is pretty clear that $$\lim_{n\to\infty}\frac{|F_p\cap[1,n]|}{n}=1-\frac{1}{p}\tag{5}$$ Divisibility by a prime $$p$$ and a prime $$q$$ are independent; that is, $$p\mid n$$ and $$q\mid n$$ if and only if $$pq\mid n$$. Thus, the density of $$F_p\cap F_q$$ is $$\lim_{n\to\infty}\frac{|F_p\cap F_q\cap[1,n]|}{n}=\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\tag{6}$$ Continuing in this manner, we get that the density of positive integers not divisible by any in a set of the primes $$\{p_i\}_{i=1}^k$$ would be $$\lim_{n\to\infty}\frac{|\bigcap_{i=1}^kF_{p_i}\cap[1,n]|}{n}=\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)\tag{7}$$ Therefore, the density of the primes not in $$\{p_i\}_{i=1}^k$$ is no greater than $$\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$$. Since the density of primes in $$\{p_i\}_{i=1}^k$$ is $$0$$, the density of all primes is no greater than $$\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$$.

If we enumerate all primes as $$\{p_i\}_{i=1}^\infty$$, using the Fundamental Theorem of Arithmetic, we get that \begin{align} \frac{1}{\prod_{i=1}^\infty\left(1-\frac{1}{p_i^\alpha}\right)} &=\prod_{i=1}^\infty\left(1+\frac{1}{p_i^\alpha}+\frac{1}{p_i^{2\alpha}}+\cdots\right)\\ &=\sum_{k=1}^\infty\frac{1}{k^\alpha}\tag{8} \end{align} As Pete mentions, since the harmonic series diverges, as $$\alpha\to1^+$$, $$(8)$$ implies that $$\prod_{i=1}^\infty\left(1-\frac{1}{p_i}\right)=0\tag{9}$$ Thus, the density of primes is $$0$$.

• +1 The technique used in the addendum is simply wonderful. I saw the first time a variant of it here Nov 2, 2014 at 16:56

Almost all of the natural numbers are composite; that is, the percentage of primes in $$\mathbb{N}$$ is $$0$$.

We know that the number of primes less than or equal to a natural number $$x$$ is asymptotic to $$x/\log(x)$$; that is, it has the same behavior for large $$x$$. Since this grows strictly slower than $$x$$, we see that the proportion of primes goes to $$0$$.

From this formula, we can also find that the proportion of primes in the natural numbers less than $$x$$ is $$1/\log(x)$$.

6.598827715%

That is, e raised to the negative e (expressed as a percentage)

The number of primes is the likelihood of zero for a Poisson Distribution with Lambda of e.

• This is a very nice number -- it appears in infinite power towers, among other applications, see oeis.org/A073230 -- but it's not the answer to this question. Some numerical evidence, if the theory wasn't making sense: $\pi(10^{25})/10^{25}\approx0.0177$, so 6.6% is way too high. Apr 29, 2014 at 22:30

While the density of primes as a percentage of all natural numbers is zero, that is merely a corollary to some of Kantor's theories about different levels of infinity: there are infinitely more natural numbers than prime numbers, so that as $N\to\infty$, density$\to 0$.

What I found more interesting was how the density of a bounded $N$ decreases as $N$ increases and remains bounded:

$25\%$ of the numbers from $1$ through $100$ inclusive are prime

$21\%$ of the numbers from $101$ through $200$ inclusive are prime

$14\%$ of the numbers from $901$ through $1,000$ inclusive are prime

$9\%$ of the numbers from $9,001$ through $10,000$ inclusive are prime

etc.

• I meant, that while primes are infinite and natural numbers are infinite, that natural numbers are at a higher level of infinity (analogous to how the real numbers are at a higher level of infinity relative to the natural numbers)
– Joe
Sep 19, 2014 at 23:36
• You are, unfortunately, sorely misguided here. This has nothing to do with Cantor's theorem; that was about cardinality, and you can map the natural numbers one-on-one to the primes and vice versa, so that there are exactly as many naturals as primes, just as there are exactly as many naturals as even numbers. Don't confuse cardinality with density. Nov 2, 2014 at 16:21