# How to identify the largest prime number below $n$ in Sieve of Eratosthenes?

How can one find the last prime number to be identified by using the Sieve of Eratosthenes Algorithm? Is there a formula to finding this number? or an explanation how this could be found? Lets say I have $$n=5000$$ as a number how can I find the largest prime below $$5000$$?

• What does "slowest" mean here? Commented Mar 20, 2013 at 16:43
• The last Prime number found in a 5000 number value. Commented Mar 20, 2013 at 16:45
• Won't that always just be the largest prime below $5000$? Commented Mar 20, 2013 at 17:00

(Trying to rescue this from the unanswered queue.)

In my way of looking at this, there is no such thing as "the slowest" or the last prime to be discovered by the Eratosthenes sieve, since after the final run-through of the process, sieving out all the multiples of $k$ (say) every number remaining which is greater than $k^2$ must be prime, and they are all found at the same time.

For a simple example, take $N=100$, we sieve out in succession, the multiples of $2$ (starting at 4), then multiples of $3$ (starting at 9), ... finally multiples of $7$ (starting at $49$). At this point we know that every remaining number greater than 49 must be prime.

Note that there is no way that the running time can be shortened by any of the last few run-throughs being unnecessary, since if $k$ is the last of the "sieving primes", $k^2$ is less than $N$ and will not previously have been sieved-out, so that every run-through is actually necessary.

Hint: If $N$ has a prime factor, then it has a prime factor that is $\leq \sqrt{N}$. Hence, to find the primes up to (say) 5000, we only need to know all the primes up to $\sqrt{5000}$, and then we can can by dividing out every subsequent number by this set of primes.

I'm not really certain what you're asking for, because your two statements are not equivalent to each other.

• My question is, how do I find the slower (last) prime number when using Sieve of Eratosthenes algorithm and whats the argumentation around it? Thanks Commented Mar 20, 2013 at 16:36