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


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

Browse other questions tagged or ask your own question.