0204. 计数质数

0204. 计数质数 #

  • 标签:数学、哈希表
  • 难度:简单

题目大意 #

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

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

示例

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

解题思路 #

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

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

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

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

考虑到如果 ix 的因数,则 $\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

思路 2:埃氏筛法 #

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

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

优化:对于一个质数 x,我们可以直接从 x * x 开始标记,这是因为 2 * x3 * 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
本站总访问量  次  |  您是本站第  位访问者