By using Prime numbers less than $\sqrt{N}$, the number of primes less than $'N'$ can be found out. Is this true or false?

I have verified it for upto from $10^1$ to $10^3$ for all the tens. So this means Number of prime numbers inside $10^{24}$ can be found out by using prime numbers less than $10^{12}$?

Whether there is more advanced of this theorem is there anywhere?


For example, $N = 100 \rightarrow \sqrt{N} = 10$

So odd Prime numbers inside $\sqrt{N}$ are $2$, $3$, $5$, $7$

Total numbers = $100$

Even numbers = $50$

Odd numbers = $49$ (Excluding 1 as we already know 1 is not a prime)

So No. of Prime numbers inside $100$ is

= $49-[(49/3)]-[((49 - (49/3))/5)]-[((49 - (49/3)-(49/5))/7)]+1 = 25$

Same can be done for $200$, $300$ ... $10^3$ ... and so on (I have verified upto $10^3$)

Note: I have not rounded off the values in the above equation!! You may get a result within a range of $5$ from the actual value($+5$ or $-5$) but I need to work more on fine tuning this.

  • $\begingroup$ Does "inside" mean "less then" or "dividing"? $\endgroup$ – Karolis Juodelė Dec 28 '12 at 10:27
  • $\begingroup$ It is difficult to understand what you mean here. What does "the number of primes inside $N$" mean? How do you find it by taking the square root of $N$? Could you provide an example? $\endgroup$ – Henning Makholm Dec 28 '12 at 10:28
  • $\begingroup$ @HenningMakholm I have provided you an example..can you look at it? $\endgroup$ – Shan Dec 28 '12 at 10:39
  • $\begingroup$ "Inside" is not a standard mathematical term in this context. What you seem to mean is "less than". $\endgroup$ – Henning Makholm Dec 28 '12 at 10:47
  • $\begingroup$ Yes!! I have edited the question.Thanks for pointing out.. $\endgroup$ – Shan Dec 28 '12 at 10:51

The number of primes less than (or equal to) $N$ is the prime-counting function, usually written $\pi(N)$.

Something like what you describe ought to work in general, at least up to an error of about $\pi(\sqrt N )$ in the worst case (and I'd expect an error of about $\sqrt{\pi(\sqrt N)}$ in the typical case).

This can be understood as using the Sieve of Eratosthenes to find the primes less than $N$, except without really finding it. It is well known that it is enough to mark multiples of primes $\le\sqrt N$ to do this; your procedure fudges the actual sieving by simply assuming that $1/p$ of all the remaining numbers will be hit when you mark multiples of $p$. This holds asymptotically (due to, for example, the Chinese Remainder Theorem), but can be off by a small number, hence the rounding errors.

The particular calculation you do looks a bit ad hoc; I think I'd write it (or something roughly equivalent to it) as

$$ \pi(N)\approx \pi(\sqrt N) + (N-\sqrt N)\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)\cdots\left(1-\frac{1}{p_k}\right) $$

where the product is over all primes up to $p_k$, the largest prime $\le\sqrt N$.

Observe that we cannot iterate this procedure to quickly pump up to $\pi(N)$ for really large $N$, because it needs not only the number of primes less than $\sqrt N$, but their actual values.

The Wikipedia article on the prime counting functions lists a number of known ways to estimate it fairly precisely.

  • $\begingroup$ So whether someone has already found out a similar function like this? I agree with what you have said about for Large N,but I think this can be expanded or modified to find for some large N easily. For example we know that,we have 25 prime numbers less than 100,So when we need to discount that we check for prime numbers less than 200.. $\endgroup$ – Shan Dec 28 '12 at 12:07
  • 1
    $\begingroup$ @Shan It's an estimate of Legendre's exact formula, stated here $\endgroup$ – WimC Dec 28 '12 at 12:12

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.