【leetcode】-204. Count Primes 计算素数

题目

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.

埃氏筛法

素数是只能被1和其本身整除的数，最小的素数就是2.

埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的，用于求一定范围内的质数。

（1）先把1删除（现今数学界1既不是质数也不是合数）
（2）读取队列中当前最小的数2，然后把2的倍数删去
（3）读取队列中当前最小的数3，然后把3的倍数删去
（4）读取队列中当前最小的数5，然后把5的倍数删去
（5）读取队列中当前最小的数7，然后把7的倍数删去
（6）如上所述直到需求的范围内所有的数均删除或读取

python代码

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

时间复杂度为O(nloglogn)，空间复杂度为O(n)。