题目

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

image.png

思路

质数：除了1和这个数本身之外，不能被其他数整除。
注：1不是质数，因为1只有一个因子。

思路一：暴力法

遍历所有数num，再遍历所有num可能的因子。
时间复杂度：O(n^2)

  1. class Solution:
  2.     def countPrimes(self, n: int) -> int:
  3.         if n <= 2: return 0
  4.         count = 1
  5.         for num in range(3, n):
  6.             factor = 2
  7.             while factor < num:
  8.                 if num % factor == 0:
  9.                     break
  10.                 else:
  11.                     factor += 1
  12.             if factor == num: count += 1
  14.         return count

思路二：优化暴力算法

细究，可以发现，假如一个数为9，那么其二分之一（4.5)后的数都已不用进行计算。
另外，所有偶数除2以外，都不可能为质数。

  1. class Solution:
  2.     def countPrimes(self, n: int) -> int:
  3.         if n < 3: return 0
  4.         count = 1
  5.         for num in range(3, n):
  6.             if num & 1 == 0:
  7.                 # 等同于 num % 2 == 0，判断n是否为偶数
  8.                 continue
  9.             factor = 3
  10.             while factor * factor <= num:
  11.                 if num % factor == 0:
  12.                     break
  13.                 else:
  14.                     factor += 2 # 循环加2，规避偶数，因为已经判断过不是偶数了
  15.             if factor * factor > num: count += 1
  16.         return count

思路三：厄拉多塞筛法

如果我们在进行顺序遍历时，每取得一个数（排除0、1），如果将它所有的倍数（排除0、1、本身）都清除，那么，剩下的数是不是必为素数？

没错，这个有趣且实用的方法便是著名的厄拉多塞筛法！

  • 选中数字2，并排除2的倍数；
  • 选中数字3，并排除3的倍数；
  • 选中数字4，并排除4的倍数；

  • ……

    1. class Solution:
    2.   def countPrimes(self, n: int) -> int:
    3.       # 厄拉多塞筛法
    4.       is_prime = [True] * (n + 2)
    5.       count = 0
    6.       for i in range(2, n):
    7.           if is_prime[i]:
    8.               count += 1
    9.           # 删除所有i的倍数的数，即相应位置的is_prime置为False
    10.           for j in range(i, n, i):
    11.               is_prime[j] = False
    13.       return count

    抄一下别人优秀的代码

    1. class Solution:
    2.   def countPrimes(self, n: int) -> int:
    3.       if n < 2: return 0
    4.       isPrimes = [1] * n
    5.       isPrimes[0] = isPrimes[1] = 0#设置0和1位为0
    6.       #下面的思路是在 2 到 根号n 的范围内，当一个数是质数，将它所有的比n小的倍数设置成0
    7.       for i in range(2, int(n ** 0.5) + 1):
    8.           if isPrimes[i] == 1:
    9.               #哇这个切片真的是pythonic
    10.               isPrimes[i * i: n: i] = [0] * len(isPrimes[i * i: n: i])
    11.       #现在每个质数位的flag为1，其余的位数为0.由于我们不需要知道质数是什么只要总数，因此直接返回list里面所有1的和就行。
    12.       return sum(isPrimes)