How to identify the slowest prime number in Sieve of Eratosthenes Algorithm how can one find the slowest prime number to be identified by using the using Sieve of Eratosthenes Algorithm? Is there a formula to finding this number? or an explanation how this could be found? Lets say I have 5000 as a number how can I find the slowest prime number?

Identify a finite n, n > 2, such that the Sieve of Eratosthenes will
  have to decide whether all the previous numbers are prime numbers or
  not and therefore the running time of the Sieve of Eratosthenes is at
  its worst for that value of n.

Thanks!
 A: 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.
A: (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.
