The sieve of Eratosthenes is O(n*log(log(n))) arithmetic
operations. Arithmetic operations themselves scale
logarithmically officially there is another log operation
in there. So within memory limits it should look
basically linear in n. I might be willing to bend a log
factor here or there. But if it isn't roughly linear in
my tests, you don't qualify.
And BTW I am not worrying about strict.
Re (tilly) 2: (Golf): Sieve of Eratosthenes