Count Primes

Question

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

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

Tags

• Hash Table
• Math

Thoughts

Followed by the hint of the question.

Code

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 0
        isPrime = [True] * n
        isPrime[0], isPrime[1] = False, False
        for i in xrange(2, int(n ** 0.5 + 1)):
            if isPrime[i]:
                isPrime[i * i : n : i] = [False] * len(isPrime[i * i : n : i])
        return sum(isPrime)