Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
What does "slowest" mean here? –  Henning Makholm Mar 20 '13 at 16:43
    
The last Prime number found in a 5000 number value. –  Christian Agius Mar 20 '13 at 16:45
1  
Won't that always just be the largest prime below $5000$? –  David Speyer Mar 20 '13 at 17:00

2 Answers 2

up vote 0 down vote accepted

(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.

share|improve this answer

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.

share|improve this answer
1  
The prime factor is $\le \sqrt{N}$, not $\lt \sqrt{N}$. –  Jonathan Rich Mar 20 '13 at 16:13
    
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 –  Christian Agius Mar 20 '13 at 16:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.