LeetCode 204. Count Primes

原题

Description:

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

求小于n（非负数）的所有质数（素数）。

思路

1. 从质数的定义出发，只能被1和自己整除，效率较低

2. 埃拉托色尼筛选法——用于求一定范围内的质数（效率高，推荐） 详戳这里百度or维基
   实现方法：
   （1）先把1删除（现今数学界1既不是质数也不是合数）
   （2）读取队列中当前最小的数2，然后把2的倍数删去
   （3）读取队列中当前最小的数3，然后把3的倍数删去
   （4）读取队列中当前最小的数5，然后把5的倍数删去
   （5）如上所述直到需求的范围内所有的数均删除或读取

代码实现

# 埃拉托色尼筛选法——用于求一定范围内的质数

# 实现一：（原始思路，循环到n，将其中循环数的倍数删去）
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        notPrime = [True]*n
        notPrime[0:2] = [False]*2
        # count = 0
        for i in xrange(2, n):
            if notPrime[i]:
                # count += 1
                j = i
                while (i * j < n):
                    notPrime[i*j] = False
                    j += 1
        return sum(notPrime)


# # 实现二：（循环到根号n后所有位置均已经完全访问，和实现一相差不大）
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        notPrime = [True]*n
        notPrime[0:2] = [False]*2
        count = 0
        for i in xrange(2, int(n**0.5)+1):
            if notPrime[i]:
                count += 1
                j = i
                while (i * j < n):
                    notPrime[i*j] = False
                    j += 1
        return sum(notPrime)


# # 实现二：（优化，效率较高）      
class Solution(object):
    def checkPrime(self, n):
        for i in range(2, int(math.sqrt(n) + 1)):
            if n%i == 0:
                return False
        return True
    
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        candidates = [True]*n
        candidates[0:2] = [False]*2
        # int(2.8) = 2; 所以需要+1
        for number in range(2, int(n**0.5) + 1):
            if candidates[number]:
                candidates[number*number:n:number] = [False]*len(candidates[number*number:n:number])
        # sum(bool)可以计算里面True的个数
        return sum(candidates)