class Solution:
# @param {integer} n
# @return {integer}
def countPrimes(self, n):
if n < 3:
return 0
primes = [True] * n
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
return sum(primes)
Fast Python Solution

class Solution(object): def countPrimes(self, n): """ :type n: int :rtype: int """ if n <= 2: return 0 prime = [True] * n prime[:2] = [False, False] for base in xrange(2, int((n  1) ** 0.5) + 1): if prime[base]: prime[base ** 2::base] = [False] * len(prime[base ** 2::base]) return sum(prime)
Your code is very brilliant! I adopt it and add some modifications.
 Because numbers LESS THAN n are considered, we can just (n  1) ** 0.5.
 When slicing, default index can be used.

here is my test about some code ,this might good for improve speed
➜ ~ python m timeit s 'int(3 ** 0.5) + 1' 100000000 loops, best of 3: 0.0119 usec per loop ➜ ~ python m timeit s 'int(3 ** 0.5 + 1)' 100000000 loops, best of 3: 0.0117 usec per loop ➜ ~ python m timeit s 'l = [False] * 1000' 'l[0] = l[1] = True' 10000000 loops, best of 3: 0.102 usec per loop ➜ ~ python m timeit s 'l = [False] * 1000' 'l[:2] = [True, True]' 10000000 loops, best of 3: 0.172 usec per loop


@sjayster If i is a prime, then i * i, i * (i +1), i * (i + 2) ... cannot be primes, as they are all divided by i.

@warm2000 2 is a prime but if n ==2 it should return 0 because we need to count the number of prime numbers less than a nonnegative number. only 1 is less then 2. And 1 is not a prime.

@sjayster
Try to go through the code and it will explain all:for i in range(2, int(n ** 0.5) + 1): if primes[i]: primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
let`s assume n == 100, we need to count all the primes which are less than 100:
when i == 2:primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
It will mark out the numbers as noneprime:
4: 100 : 2 > 4,6,8,10,12,14 ... 100
which makes prime[4] =False, prime[6]=False, prime[8]=False....similarly:
when i ==3:
9: 100 : 3  > 9,12,15,18,21,24... 96, 99
when i == 4:
16: 100 :4 > 16,20,24,28.... 96,100
...
...
So if n is not a prime, prime[n] = False, otherwise, prime[n] = True, which is 1 in math.
So sum the whole list, you will get the count of primes.

@tusizi said in Fast Python Solution:
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
for j in range(i * i, n, i): primes[j] = False
Much cleaner this way.