前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode每日一题:204. 计数质数

leetcode每日一题:204. 计数质数

作者头像
用户3578099
发布2020-12-14 14:58:02
4180
发布2020-12-14 14:58:02
举报
文章被收录于专栏:AI科技时讯

题目:

https://leetcode-cn.com/problems/count-primes/

思路:

质数:指在大于 1 的自然数中,只能被 1 和自身整除的自然数。

根据质数的概念,我们首先能够想到的就是直接枚举。

对于每个数 i,我们可以枚举 [2, i-1]区间的任意一个数 j,判断 i能否被 j 整除。这里需要注意的是,这里时间复杂度最差的情况下为 O(n)。但 n 在这里也是一个比较大的数字,单单对一个数字进行判断时,时间复杂度到 O(n)并不理想。

代码语言:javascript
复制
class Solution:
    def countPrimes(self, n: int) -> int:
        # 质数的属性  只能被1和自己整除
        count = 0
        # bf
        for i in range(2, n):
            flag = 0
            for j in range(2, i):
                if i % j == 0:
                    flag = 1
                    break
            if flag == 0:
                count += 1
        return count

枚举 [2, i-1] 区间的任意一个数 j,判断 i 能否被 j整除时,我们可以发现,如果 i 能够被 j整除,那么这里的商也一定能够整除 i,即是 i 也能够被i/j 整除。那么我们只要判断 i和i/j其中一个能否整除 i即可。此时我们只要选择判断两者中的较小值,而且我们可以发现较小值一定是落在区间 [2, sqrt(i)]。那么判断每个数i ,枚举时只需要枚举 [2, sqrt(i)]中的数即可。那么此时判断的时间复杂度则可以优化至 O(sqrt(n))

具体的代码实现如下

代码语言:javascript
复制
class Solution:
    def countPrimes(self, n: int) -> int:
        # 质数的属性  只能被1和自己整除
        # 缩短一半
        def is_prime(num):
            j = 2
            while j*j <= num:
                if num % j == 0:
                    return False
                j += 1
            return True

        count = 0
        for i in range(2, n):
            if is_prime(i):
                count += 1
        return count

埃氏筛

这里说下埃氏筛,这里先放一张关于埃氏筛思路的图片(来源:维基百科)

埃氏筛的原理:从 2 开始,将每个质数的倍数都标记为合数。同样的,标记到 sqrt(n)停止。

假设一个数 i 为质数时,那么此时大于 i且是 i的倍数的数一定不是质数,例如 2i,3i...。那么我们将这些不是质数的数进行标记。

这里需要注意,标记应该从 i * i开始,而不是 2 * i开始。因为对于每个数 i 来说,枚举是从小到大的,此时前面数字的倍数都已经进行了标记。对于 i 而言,2 * i也肯定会被在枚举数字 2 时进行标记,[2, i) 区间的数同理。

代码语言:javascript
复制
 class Solution:
    def countPrimes(self, n: int) -> int:
        # 质数的属性  只能被1和自己整除
        is_prime = [1] * n
        count = 0
        for i in range(2, n):
            if is_prime[i]:
                count += 1
                # 从 i*i 开始标记
                for j in range(i*i, n, i):
                    is_prime[j] = 0
        return count
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-12-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 AI科技时讯 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档