204. Count Primes

Description

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.

Solutions

　　题意就是找比 $n$ 小的质数的个数了，所谓质数就是除了 1 和其本身不能被其他整除的数。

1. Brute Force

　　想先快速实现一个暴力的版本，结果超时了：

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 1:
            return 0
        count = 0
        for i in range(1, n):
            if self.isPrimes(i):
                count += 1
        return count
    
    def isPrimes(self, num):
        if num <= 1:
            return False

        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True

2. 埃拉托斯特尼筛法

　　埃拉托斯特尼筛法就是用来解决这个问题，以此从小到大找到所有质数的倍数给全部删掉即可。

# Time: O(nloglogn)
# Space: O(n)
class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        tags = [True for _ in range(n)]
        tags[0], tags[1] = False, False
        sqrtn = int(round(n ** 0.5))
        for i in range(2, sqrtn + 1):
            if tags[i]:
                for j in range(i * i, n, i):
                    tags[j] = False
        
        return sum(tags)
# 20/20 cases passed (500 ms)
# Your runtime beats 63.22 % of python3 submissions
# Your memory usage beats 62.07 % of python3 submissions (27.6 MB)

　　牛人优化之后的版本更快：

class Solution(object):

    
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 2:
            return 0
        
        s = [True] * n
        s[0] = s[1] = False
        sqrtn = int(round(n**0.5))
        for i in xrange(2, sqrtn + 1): 
            if s[i]:
                s[i*i: n: i] =  [False] * len(xrange(i*i, n, i))
        return s.count(True) 
# Runtime: 132 ms, faster than 98.74% of Python online submissions for Count Primes.
# Memory Usage: 34.9 MB, less than 76.32% of Python online submissions for Count Primes.

References

204. Count Primes