第四章：如何高效寻找素数

labuladong如何高效寻找素数

204. 计数质数

统计所有小于非负整数 n 的质数的数量

• 初始化时，给每个位置立一个flag，并初始化为1
• 遍历时，对于i而言：
  • 如果这个位置的flag为1，说明数字 i 没有被比 i 小的数整除过，说明它是质数，计数器+1。
  • i 的倍数一定不是质数，将这些数的flag设置为0

一切尽在sieve of Eratosthenes算法的图中

class Solution:
    def countPrimes(self, n) :
        #给每个位置立一个flag，初始化为1
        isPrimes = [1] * n
        #result，输出的质数总个数的计数器，初始化为0
        res = 0
        #循环，从最小质数i开始到n循环
        for i in range(2, n):
            #如果这个位置的flag为1，说明数字 i  没有被比 i 小的数整除过，说明它是质数，计数器+1
            if isPrimes[i] == 1: res += 1

            #下面这几步的思路是， i 的倍数一定不是质数，将这些数的flag设置为0
            #设置倍数 j ，初始化与 i 相等。 因为i也是一点点加上来的，比如 i=5的时候，i 的4倍一定在 i=4 时已经设置为0过。
            j = i
            # 因为统计的是所有小于非负整数 n 的质数的数量，当 i 的 j 倍 >=n 时，跳出循环
            while i * j < n:
                #设置i 的 j 倍的flag为0
                isPrimes[i * j] = 0
                # 自增，下一个找 j+1 倍
                j += 1
        #返回结果
        return res