# Sieve of Eratosthenes Algorithm, Identifying a number n, n>2 and decide whether or not it is a prime number in O(n) time

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.

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