I use array with length of n/2 for sieve, and got MLE every time.

I tried same logic with Python and it's accepted. Actually, according to posts at discussion, I saw Python code with n length list got accepted.

I assume Python and Ruby should not have similar limits, right?

Are you too strict to rubiers?

Code:

```
# @param {Integer} n
# @return {Integer}
def count_primes(n)
return 0 if [0, 1, 2].include? n
upper = n / 2
stop = (Math.sqrt(n) - 1) / 2
sieve = Array.new(upper) {true}
x = 1
while x <= stop
if sieve[x]
step = 2 * x + 1
s = x + step
while s < upper
sieve[s] = false
s += step
end
end
x += 1
end
sieve.count {|x| x}
end
```