目录

0204:计数质数(★)

力扣第 204 题

题目

给定整数 n ,返回 所有小于非负整数 n 的质数的数量

示例 1:

输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2:

输入:n = 0
输出:0

示例 3:

输入:n = 1
输出:0

提示:

  • 0 <= n <= 5 * 106

相似问题:

分析

本题有个经典的埃氏筛法:

  • 从 2 开始遍历到 n
  • 遍历到质数 x 时 ,将之后 x 的倍数都标记为 0
  • 遍历到数 x,假如 x 还未标记,x 即是质数

解答

1
2
3
4
5
6
7
class Solution:
    def countPrimes(self, n: int) -> int:
        f = [0]*2+[1]*(n-2)
        for i in range(2,isqrt(n)+1):
            if f[i]:
                f[i*i:n:i] = [0]*((n-i*i-1)//i+1)
        return sum(f)

757 ms

*附加

#1

基于埃氏筛法还有个很巧妙的动态规划方法。

  • 令 f[p][v] 代表埃氏筛法遍历到数 p 时,[2, v] 内还未标记的个数
  • 如果 p*p > v 或者 p 是合数:
    • p 筛不到数,f[p][v] = f[p-1][v]
  • 如果 p*p <= v 且 p 是质数:
    • 令 g(x) 代表 x 的最小质因数
    • p 能筛掉合数 C=p*x,当且仅当 g(x)>=p
    • p 能筛掉的合数个数
      • = 满足 p*x<=v 且 g(x)>=p 的 x 的个数
      • = [p, v//p] 内还未标记的个数
      • = f[p-1][v//p] - f[p-1][p-1]
    • f[p][v] = f[p-1][v] - (f[p-1][v//p] - f[p-1][p-1])
  • 质数不会被标记,所以可以用 f[p-1][p]>f[p-1][p-1] 判断 p 是否质数
  • 要求的即是 $f[\lfloor \sqrt n \rfloor][n]$
  • 注意递推时 f[p][v] 涉及到的 v 不是 [2,n]
    • 要么 v<=$\sqrt n$,要么 v 是 n//p 的形式
    • v 的个数是 $O(\sqrt n)$
  • 所以总的时间复杂度为 O(N)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def countPrimes(self, n: int) -> int:
        n -= 1
        if n < 2:
            return 0
        r = isqrt(n)
        V = list(range(1,n//r))+[n//x for x in range(r,0,-1)]
        f = [{} for _ in range(r+1)]
        f[1] = {v: v-1 for v in V}
        for p in range(2, r+1):
            for v in V:
                f[p][v] = f[p-1][v]
                if p*p <= v and f[p-1][p]>f[p-1][p-1]:
                    f[p][v] -= f[p-1][v//p]-f[p-1][p-1]
        return f[r][n]

4224 ms

#2

  • 注意反向遍历 v 就可以优化为一维数组
  • 当 p*p > v 或者 p 是合数时,可以直接跳出遍历,极大地优化时间
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def countPrimes(self, n: int) -> int:
        n -= 1
        if n < 2:
            return 0
        r = isqrt(n)
        V = [n//x for x in range(1,r)] + list(range(n//r,0,-1))
        f = {v: v-1 for v in V}
        for p in range(2, r+1):
            for v in V:
                if p*p>v or f[p]==f[p-1]:
                    break
                f[v] -= f[v//p]-f[p-1]
        return f[n]

158 ms