# Count the number of prime numbers less than a non-negative number, n.
#
# Example:
#
# Input: 10
# Output: 4
# Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<3:
            return 0
        res=[True]*n
        res[0]=res[1]=False
        for i in range(2,int(n**0.5)+1):
            if res[i]==True:
                for j in range(i,(n-1)/i+1):
                    res[i*j]=False
        return sum(res)