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.

I have a question which I can't figure out what exactly its the outcome.

For the Sieve of Eratosthenes, identify a number n, n > 2, such that the Sieve of Eratosthenes will be able to decide whether or not it is a prime number in O(n) time.

Does anyone has any idea about this? Thanks in advance!

share|improve this question
3  
Not sure this is the meaning of the question, but it sounds like any even number. Since it gets "crossed out" in the first iteration of the sieve. –  Yoni Rozenshein Mar 20 '13 at 16:57
1  
Actually I was thinking that its '3' since its the first prime number that sieve finds which is bigger then 2 (as it should be n>2). The thing is that I'm not sure how to explain it! –  Christian Agius Mar 20 '13 at 17:01
1  
Yeah, but if you run the sieve all the way up to ten billion, it'll take about five billion iterations until you get to cross out 3. So, not exactly $O(n)$ where $n=3$. –  Yoni Rozenshein Mar 20 '13 at 17:04
2  
It means there is some constant $c$ such that the amount of time (i.e. computation steps) that the algorithm takes to finish does not exceed $cn$. In this particular question, I am not sure $O$-notation makes sense at all though, because we know nothing about the relation between $n$ and the size of the sieve we're running. –  Yoni Rozenshein Mar 20 '13 at 17:17
1  
It doesn't make sense to speak of $O(n)$ time unless $n$ is variable. If $n$ is constant, the amount of time required by Sieve of Eratosthenes to determine primality is also a constant. Most likely your problem was to find a family of numbers greater than two whose primality is determined in $O(n)$ time. The even numbers $2n$ are such a family. –  hardmath Mar 20 '13 at 17:50

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.