Count Primes

Count the number of prime numbers less than a non-negative number n.

埃拉托斯特尼筛法： http://open.163.com/movie/2012/10/0/6/M99VJKUHC_M9ENDUB06.html

首先使所有数都为prime（true），循环所有数，使此数平方以后的所有此数的倍数都为false

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        isPrime = [True] * max(n, 2)
        isPrime[0], isPrime[1] = False, False
        x = 2
        while x*x < n:
            if isPrime[x]:
                p = x*x
                while p < n:
                    isPrime[p] = False
                    p += x
            x += 1
        return sum(isPrime)