# Fast Python Solution

• ``````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)``````

• ``````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)
``````

1. Because numbers LESS THAN n are considered, we can just (n - 1) ** 0.5.
2. When slicing, default index can be used.

• is 2 a prime？ so if n ==2 would return 1?

• 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``````

• Could someone please explain me what this line does?
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])

• Could not be better!

• @warm2000 the description said that `less than n`

• could I omit the `n < 3 ` judgement? I tried and was accepted

• if you try:

primes = [1,2,3,4,5,6,7,8,9,10]

primes[3:10:2] = [0]*len(primes[3:10:2])

print primes

you will see what's going on.

• Genius man! perfectly solved the "time limit exceeds" issue.

• Nice use of the eratosthenes theorem! (ง •̀_•́)ง

• This post is deleted!

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

• Great solution.
I think we can calculate len(primes[i*i:n:i]) ourself for optimization

``````...
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i: n: i] = [False] * ((n-i*i-1)/i + 1)
...
``````

The code will beat about 98% after the modification.

• @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 non-negative 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 none-prime:
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.

• in

``````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])
``````

why it must multiply with lenth???

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

• @david148877 len() counts how many of the items in primes[], thus replace them with 0/False.

• It should be O(n) solution, right? because it almost only visit each number once

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