0204：计数质数（★）

2015-07-23 约 705 字预计阅读 2 分钟次阅读

力扣第 204 题

题目

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

示例 1：

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

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

0 <= n <= 5 * 10⁶

相似问题：

分析

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

从 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

目录

0204：计数质数（★）

题目

分析

解答

*附加

#1

#2