Leetcode 204 - Count Primes

DocumentsAlgorithms
Algorithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. Explanation
  3. 3. Code

Question

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.

Explanation

判断一个数是否是质数最简单的方法是用所有比他小的正整数（1除外）去除它，如果都不能除尽，则这个数是质数，但是这样的时间复杂度将会是$O(n^2)$。这里需要用到埃拉托斯特尼筛法减少循环次数。埃拉托斯特尼筛法是从2开始，将2的正整数倍的数都标记为False，在之后的遍历过程中，标记为False的数将不再做素数的判断，因为他们都能被2整除。标记完之后，继续对下一个标记为True的数字（这里是3）进行筛选，直到最后一个数。如下为动态演示：


source from wikipedia

这样筛选还是包含了一些不必要的计算，因为一个合数 $n$ 的因子必然小于 $ \sqrt{n} $ ，因此对于 $ n \in {1,N} $ ， 只需要排除小于 $ \sqrt{N}+1 $ 的素数的倍数。至于大于等于 $ \sqrt{n}+1 $ 的素数，它们的倍数要么被更小的素数筛完，要么大于 $N$ ，因此无需判断。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 2:
            return 0
        nSqrt = int(n**0.5)+1
        primeList = [True] * n
        primeList[0:2] = [False] * 2
        for i in range(nSqrt):
            if primeList[i]:
                primeList[2*i:n:i] = [False]*len(range(2*i,n,i))
        res = primeList.count(True)
        return res
Comments