204. Count Primes

统计小于非负整数n的素数的个数

提示：n的范围是100,000到5,000,000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 6 star, 没做出来
        # 用一个长度为n的列表，记录每个索引是否是素数，首先将其全部标记为1，
        # 然后由于0，1都不是素数，将前两个标记为0，从2开始到根号n, 将这些数的所有倍数全部排除，剩下的就是素数了
        if n < 3:
            return 0
        is_prime = [1 for _ in range(n)]
        is_prime[:2] = [0, 0]
        for i in range(2, int(n ** 0.5) + 1):
            if is_prime[i] == 1:
                for j in range(2 * i, n, i):
                    is_prime[j] = 0
        return sum(is_prime)