0
$\begingroup$

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?

Example

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.

$\endgroup$
11
  • $\begingroup$ Does "inside" mean "less then" or "dividing"? $\endgroup$ Commented Dec 28, 2012 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$ Commented Dec 28, 2012 at 10:28
  • $\begingroup$ @HenningMakholm I have provided you an example..can you look at it? $\endgroup$
    – Shan
    Commented Dec 28, 2012 at 10:39
  • $\begingroup$ "Inside" is not a standard mathematical term in this context. What you seem to mean is "less than". $\endgroup$ Commented Dec 28, 2012 at 10:47
  • $\begingroup$ Yes!! I have edited the question.Thanks for pointing out.. $\endgroup$
    – Shan
    Commented Dec 28, 2012 at 10:51

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\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
    Commented Dec 28, 2012 at 12:07
  • 2
    $\begingroup$ @Shan It's an estimate of Legendre's exact formula, stated here $\endgroup$
    – WimC
    Commented Dec 28, 2012 at 12:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .