Leetcode 204. Count Primes

https://leetcode.com/problems/count-primes/

Brute force is not acceptable. The solution is really smart, while there are still spaces to improve.

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param {integer} n
    # @return {integer}
    def countPrimes(self, n):
        if n <= 2:
            return 0
        
        is_prime = [True] * n
        
        num = 0
        for i in xrange(2, n):
            if is_prime[i]:
               num += 1
               for j in xrange(i+i, n, i):
                   is_prime[j] = False
                   
        return num

Run Time: 804 ms