# Python easy to understand solution.

• ``````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, (n-1)//i+1):
res[i*j] = False
return sum(res)``````

• I think j in second loop should start from i instead of 2

``````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(i, (n-1)/i+1):
res[i*j] = False
return sum(res)``````

• I used range instead of xrange and got Memory Limit Exceeded. No idea why I had to use xrange for it work properly.

• @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.

• @persianPanda That's interesting! Thanks for letting me know!

• @caikehe Is this dynamic programming?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.