def countPrimes(self, n):
if n <= 2:
return 0
res = [True] * n
res[0] = res[1] = False
for i in xrange(2, n):
if res[i] == True:
for j in xrange(2, (n1)//i+1):
res[i*j] = False
return sum(res)
Python easy to understand solution.

@glang range(1,n) allocates memory to store all the 1...n values. But xrange(1,n) generates them on the fly: in each iteration the next number is generated. So it is better memory wise.

