0204. 计数质数

0204. 计数质数 #

  • 标签:数组、数学、枚举、数论
  • 难度:简单

题目大意 #

描述:给定 一个非负整数 $n$。

要求:统计小于 $n$ 的质数数量。

说明

  • $0 \le n \le 5 * 10^6$。

示例

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

解题思路 #

思路 1:枚举算法(超时) #

对于小于 $n$ 的每一个数 $x$,我们可以枚举区间 $[2, x - 1]$ 上的数是否是 $x$ 的因数,即是否存在能被 $x$ 整数的数。如果存在,则该数 $x$ 不是质数。如果不存在,则该数 $x$ 是质数。

这样我们就可以通过枚举 $[2, n - 1]$ 上的所有数 $x$,并判断 $x$ 是否为质数。

在遍历枚举的同时,我们维护一个用于统计小于 $n$ 的质数数量的变量 cnt。如果符合要求,则将计数 cnt 加 $1$。最终返回该数目作为答案。

考虑到如果 $i$ 是 $x$ 的因数,则 $\frac{x}{i}$ 也必然是 $x$ 的因数,则我们只需要检验这两个因数中的较小数即可。而较小数一定会落在 $[2, \sqrt x]$ 上。因此我们在检验 $x$ 是否为质数时,只需要枚举 $[2, \sqrt x]$ 中的所有数即可。

利用枚举算法单次检查单个数的时间复杂度为 $O(\sqrt{n})$,检查 $n$ 个数的整体时间复杂度为 $O(n \sqrt{n})$。

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def isPrime(self, x):
        for i in range(2, int(pow(x, 0.5)) + 1):
            if x % i == 0:
                return False
        return True

    def countPrimes(self, n: int) -> int:
        cnt = 0
        for x in range(2, n):
            if self.isPrime(x):
                cnt += 1
        return cnt

思路 1:复杂度分析 #

  • 时间复杂度:$O(n \times \sqrt{n})$。
  • 空间复杂度:$O(1)$。

思路 2:埃氏筛法 #

可以用「埃氏筛」进行求解。这种方法是由古希腊数学家埃拉托斯尼斯提出的,具体步骤如下:

  • 使用长度为 $n$ 的数组 is_prime 来判断一个数是否是质数。如果 is_prime[i] == True ,则表示 $i$ 是质数,如果 is_prime[i] == False,则表示 $i$ 不是质数。并使用变量 count 标记质数个数。
  • 然后从 $[2, n - 1]$ 的第一个质数(即数字 $2$) 开始,令 count 加 $1$,并将该质数在 $[2, n - 1]$ 范围内所有倍数(即 $4$、$6$、$8$、…)都标记为非质数。
  • 然后根据数组 is_prime 中的信息,找到下一个没有标记为非质数的质数(即数字 $3$),令 count 加 $1$,然后将该质数在 $[2, n - 1]$ 范围内的所有倍数(即 $6$、$9$、$12$、…)都标记为非质数。
  • 以此类推,直到所有小于或等于 $n - 1$ 的质数和质数的倍数都标记完毕时,输出 count

优化:对于一个质数 $x$,我们可以直接从 $x \times x$ 开始标记,这是因为 $2 \times x$、$3 \times x$、… 这些数已经在 $x$ 之前就被其他数的倍数标记过了,例如 $2$ 的所有倍数、$3$ 的所有倍数等等。

思路 2:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def countPrimes(self, n: int) -> int:
        is_prime = [True] * n
        count = 0
        for i in range(2, n):
            if is_prime[i]:
                count += 1
                for j in range(i * i, n, i):
                    is_prime[j] = False
        return count

思路 2:复杂度分析 #

  • 时间复杂度:$O(n \times \log_2{log_2n})$。
  • 空间复杂度:$O(n)$。
本站总访问量  次  |  您是本站第  位访问者