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.

  • 0
    Does "inside" mean "less then" or "dividing"?2012-12-28
  • 0
    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?2012-12-28
  • 0
    @HenningMakholm I have provided you an example..can you look at it?2012-12-28
  • 0
    "Inside" is not a standard mathematical term in this context. What you seem to mean is "less than".2012-12-28
  • 0
    Yes!! I have edited the question.Thanks for pointing out..2012-12-28
  • 0
    Could you please explain your calculation for the "Number of prime numbers inside 100"? I don't see how you get 25 for the value of that expression, as you seem to be adding 4 quantities which are positive, and the first is already 49.2012-12-28
  • 0
    @OldJohn Edited the example. 49-16-6-3+1=25 (I used a $+$ symbol instead of $-$ symbol)2012-12-28
  • 0
    Best I can guess, you're using the idea behind the [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_eratosthenes). First you count the number of odd numbers, then take away the multiples of 3, then take away multiples of 5 from that, and so on...2012-12-28
  • 0
    Not at all..because I am taking Prime numbers less than $\sqrt{N}$ where Sieve of Eratosthenes is not upto a certain number. Basically all the numbers inside a 'N' can be formed by number inside < N2012-12-28
  • 0
    It looks to me that you are trying to derive something like Legendre's method of finding the number of primes up to $x$, as explained [here](http://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_.CF.80.28x.29)2012-12-28
  • 0
    @OldJohn Don't know..I am not able to understand it..whether you have some real example for that?2012-12-28

1 Answers 1

3

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.

  • 0
    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..2012-12-28
  • 1
    @Shan It's an estimate of Legendre's exact formula, stated [here](http://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_.CF.80.28x.29)2012-12-28