number of primes less than a number $N$ is $\tfrac{N}{\log(N)}$ ??

838 Views Asked by At

In my lecture notes it says that for $N \in \Bbb N$ there are $\tfrac{N}{\log(N)}$ primes which are less than $N$.

But say $N=20$, the primes less than $20$ are $1,2,3,5,7,11,13,17,19$, so there are 9 primes less than $20$. But $\tfrac{20}{\log(20)}=15.372$. Which is 1) a decimal number and 2) larger than 9 !

What's going on here, the statement in my notes must be written incorrectly right ?

1

There are 1 best solutions below

0
On BEST ANSWER

Your lectures notes are covering what is known as the prime number theorem.

Let $\pi(N)$ denote the number of primes $\leq N$. The prime number theorem states that

$$\pi(N) \sim \frac{N}{\log N} \ \text{as} \ N \to +\infty$$

So, if you compare $\pi(20)$ with ${20}/{\log 20}$, you will find that $\pi(20)=8$ while ${20}/{\log 20}\approx 6.676$. But, what would happen if we increase $N$ to $100, 1000,$ or $10000$?

If you look at larger numbers of $N$,

\begin{array}{|c|} \hline N& \pi(N) & N/\log{N} \\ \hline 1000& 168& 145&\\ \hline 10000& 1229& 1086&\\ \hline 100000& 9592& 8686&\\ \hline 1000000& 78498& 72382&\\ \hline 10000000& 664579& 620420&\\ \hline 10000000& 5761455& 5428681&\\ \hline \end{array}

then you will see that $\pi(N)$ gets closer and closer to $\frac{N}{\log N}$ as $\ N \to +\infty$. This is why

$$\lim_{N\to\infty}\frac{\;\pi(N)\;}{\; \frac{N}{\log(N)}\;} = 1$$

The above relation also shows that $\pi(N)$ and $\frac{N}{\log N}$ are asymptotically equivalent which means that they will essentially become equal as $N$ becomes arbitrarily large.

Therefore, you should adjust your lecture notes to account for $\ N \to +\infty$ and then describe the relation hidden in $\pi(N) \sim \frac{N}{\log N}$.