204. Count Primes-计数质数

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

Example 1:
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:
Input: n = 0
Output: 0

Example 3:
Input: n = 1
Output: 0

Constraints:

• 0 <= n <= 5 * 10^6

Solution in python:
1.Brute force

class Solution:
    def countPrimes(self, n: int) -> int:
        def isPrime(n):
            if n <= 1:
                return False
            i = 2
            while i <= int(sqrt(n)):
                if n % i == 0:
                    return False
                i += 1
            return True

        if n <= 2: return 0
        count = 0
        i = 1
        while i < n:
            if isPrime(i):
                count += 1
            i += 2
        return count 

2.Primer sieve

class Solution:
    def countPrimes(self, n: int) -> int:
        alist = [1 for i in range(n)]
        if n <= 2:
            return 0
        alist[0], alist[1] = 0, 0
        for i in range(2, n):
            if alist[i] == 1:
                k = 2
                while i*k < n:
                    alist[i*k] = 0
                    k += 1
        return sum(alist)