计算机创新协会冬令营——暴力枚举题目05

这道题挺基础但是挺多坑的。(•́へ•́╬)

题目

204. 计数质数 - 力扣(LeetCode)

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

示例 

示例 1:

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

示例 2:

输入:n = 0
输出:0

示例 3:

输入:n = 1
输出:0

提示:

注意这玩意儿,好东西

  • 0 <= n <= 5 * 10^{6}

 


Java解不出来法:普通暴力枚举

emmm,挨个找,挨个判断是吧,应该就可以得出答案

但是如果你写下了如下的代码,就会发现超时啦@!

class Solution {
    public int countPrimes(int n) {
        int res = 0;
        for (int i = 2; i < n; i++) {
            boolean flag = true;
            for (int j = 2; j < n + 1 / 2; j++) {
                if (flag && i != j && i % j == 0){
                    flag = false;
                }
            }
            if (flag){
                res++;
            }
        }
        return res;
    }
}

 

然后冥思苦想得出了如下的枚举优化 

class Solution {
    public static int countPrimes(int n) {
        int count = 0;
        for (int i = 2; i < n; i++) {
            boolean sign = true;
            for (int j = 2; j <  i + 1 / 2; j++) {
                if (i % j == 0) {
                    sign = false;
                    break;
                }
            }
            if (sign){
                count++;
            }
        }
        return count;
    }
}

这里用了break跳过了那么多次循环,甚至第二个循环从 n + 1 / 2 优化到了 i+ 1 / 2,哇,无懈可击对吧!!!我也觉得

送给你

来说题目里 n 的规模达到 10^{5}及以上时,需要实现的程序的时间复杂度 最高 只能是 O(n\log n)的。但还有是有个别“恶心”的题目是n\log\log n,比如这道题^_^; : (

发现并不简单

6666666666666666666666666666666666666666666666

玩啥啊这还

搞不了

官方题解

class Solution {
    public int countPrimes(int n) {
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            ans += isPrime(i) ? 1 : 0;
        }
        return ans;
    }

    public boolean isPrime(int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

不是兄弟我用官方题解还治不了你》?????????????????

搞笑

?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

我服

然后就裂开了

然后我就疯狂查资料啊老铁

然后让我发现了一个好东西

埃拉托斯特尼筛法

素数就是质数

维基百科的解释是:

考虑这样一件事情:对于任意一个大于  的正整数 ,那么它的  倍就是合数()。利用这个结论,我们可以避免很多次不必要的检测。

如果我们从小到大考虑每个数,然后同时把当前这个数的所有(比自己大的)倍数记为合数,那么运行结束的时候没有被标记的数就是素数了。

也就是:

看下面维基百科的动画:

注意每次找当前素数 x 的倍数时,是从 x^{2}开始的。因为如果 x>2,那么 2 * x 肯定被 2 给判断过一次了,最小未被过滤的肯定是 x^{2}.

哈哈哈哈哈哈哈哈

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }
        boolean[] isPrime = new boolean[n];
        // 初始化所有数为质数
        for (int i = 2; i < n; i++) {
            isPrime[i] = true;
        }
        // 埃拉托斯特尼筛法
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        // 统计质数的数量
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }
        return count;
    }
}

现在肯定跑的出来了吧,哈哈哈哈哈哈哈哈哈哈哈哈

总结

下次写题先看官方题解谢谢

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/294322.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

手机与电脑投屏互联方案

手机 to 电脑 无线显示器 搜索"无线显示器"找到系统自带的应用 没有的话, 可能需要安装一下 电脑上打开无线显示器 手机中打开投屏 就投上去了, 感觉很卡, 不是很流畅,但是是系统自带的功能, 比较方便 无法连接时可以检查一下这里的设置 scrcpy screen copy 屏幕…

Socket与TCP的关系

前言 相信大家对于TCP已经非常熟悉了&#xff0c;学习过计算机网络的同学对于它的连接和断开流程应该已经烂熟于心了吧。 那么Socket是什么&#xff1f; Socket是应用层与TCP/IP协议簇通信的中间软件抽象层&#xff0c;它是一组接口。在设计模式中&#xff0c;Socket其实就是…

2023 北京国炬软件年度总结—JeecgBoot与敲敲云

2023年对于北京国炬软件公司来说是一个充满成就和创新的一年。 我们成功推出了APass零代码平台—敲敲云&#xff0c;一款能够在5分钟内搭建应用的新一代零代码平台。自2023年1月1号正式上线以来&#xff0c;敲敲云已经突破了10万注册用户&#xff0c;并与数百家战略合作伙伴达…

解决mock单元测试中 无法获取实体类xxx对应的表名

错误描述&#xff1a;在执行单元测试时&#xff0c;执行到new Example时抛出异常&#xff0c;提示无法获取实体类xxx对应的表名 Example example new Example(ServeSubscribeRecord.class);Example.Criteria criteria example.createCriteria();criteria.andEqualTo("se…

记一次:Python的学习笔记四(Gatway网关配置python服务)

前言&#xff1a;如果我后台是spring cloud&#xff0c;单独一个模块是Python写的服务如何集成进来呢&#xff1f;于是乎如下 1、gatway网关配置 # python服务- id: xxx-pythonuri: lb://xxx-pythonpredicates:- Path/python/**filters:- StripPrefix1 2、请求网关地址&#…

如何在 Ubuntu 20.04 上安装和使用 Docker

前些天发现了一个人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;最重要的屌图甚多&#xff0c;忍不住分享一下给大家。点击跳转到网站。 如何在 Ubuntu 20.04 上安装和使用 Docker 介绍 Docker是一个可以简化容器中应用程序进程管理过程的应用程序。…

网络割接为什么经常是半夜进行?

你们好&#xff0c;我的网工朋友。 假设你最近遇到了一个客户&#xff0c;客户有个新的园区刚刚建成&#xff0c;园区内包括建筑物若干&#xff0c;地理覆盖面也较广&#xff0c;园区建成后&#xff0c;肯定是需要一个专用网络的&#xff0c;用于承载公司的业务流量。 这时候&…

芯课堂 | LVGL基础知识(三)

概述 LVGL进度条对象上有一个背景和一个指示器。指示器的宽度根据进度条的当前值进行设置。 如果对象的宽度小于其高度&#xff0c;则可以创建垂直进度条。 不仅可以设置进度条的结束值&#xff0c;还可以设置进度条的起始值&#xff0c;从而改变指示器的起始位置。 LVGL进度…

【ESP32接入语言大模型之通义千问】

1. 通义千问 讲解视频&#xff1a; ESP32接入语言大模型之通义千问 随着人工智能技术的不断发展&#xff0c;自然语言处理领域也得到了广泛的关注和应用。通义千问由阿里云开发&#xff0c;目标是帮助用户获得准确、有用的信息&#xff0c;解决他们的问题和困惑&#xff0c;也…

C# OpenCvSharp DNN FreeYOLO 目标检测

目录 效果 模型信息 项目 代码 下载 C# OpenCvSharp DNN FreeYOLO 目标检测 效果 模型信息 Inputs ------------------------- name&#xff1a;input tensor&#xff1a;Float[1, 3, 192, 320] --------------------------------------------------------------- Outp…

C# OpenCvSharp DNN Gaze Estimation

目录 介绍 效果 模型信息 项目 代码 frmMain.cs GazeEstimation.cs 下载 C# OpenCvSharp DNN Gaze Estimation 介绍 训练源码地址&#xff1a;https://github.com/deepinsight/insightface/tree/master/reconstruction/gaze 效果 模型信息 Inputs ----------------…

书生·浦语大模型实战营第一次课堂笔记

书生浦语大模型全链路开源体系。大模型是发展通用人工智能的重要途径,是人工通用人工智能的一个重要途径。书生浦语大模型覆盖轻量级、重量级、重量级的三种不同大小模型,可用于智能客服、个人助手等领域。还介绍了书生浦语大模型的性能在多个数据集上全面超过了相似量级或相近…

PMP证书考下来要多少费用?

PMP考试形式分为&#xff1a;笔试、机考。PMP考试这里只着重介绍笔试&#xff08;大陆地区目前都是笔试&#xff09;&#xff1a; PMP认证考试在大陆内的考试一般一年举行四次&#xff0c;分别在3、6、9、12月份。2024年考试时间是3、5、8、11月份。 考试方式是笔试。考试改版…

stable diffusion 人物高级提示词(四)朝向、画面范围、远近、焦距、机位、拍摄角度

一、朝向 英文中文front view正面Profile view / from side侧面half-front view半正面Back view背面(quarter front view:1.5)四分之一正面 prompt/英文中文翻译looking at the camera看向镜头facing the camera面对镜头turned towards the camera转向镜头looking away from …

制造业企业使用SD-WAN的意义

在信息技术和制造业越来越密不可分的背景下&#xff0c;推进智能制造&#xff0c;需要升级网络支撑工业互联网平台的搭建、数字化车间、智能工厂的建设等等。SD-WAN的应用使得制造业企业网络升级更为方便、快捷、低成本。 制造业企业总部、分支机构、工厂一般分布较为分散&…

大数据开发个人简历范本(2024最新版-附模板)

大数据开发工程师个人简历范本> 男 22 本科 张三 计算机科学与技术 1234567890 个人概述 具备深入的Hadoop大数据运维工程师背景&#xff0c;熟悉相关技术和工具 具备良好的团队合作能力&#xff0c;善于沟通和协作 具有快速学习新知识和解决问题的能力 对于数据科学…

Kafka 如何保证消息不丢失?

今天分享的这道面试题&#xff0c;是一个工作 2 年的小伙伴私信给我的。 我觉得这个问题比较简单&#xff0c;本来不打算说&#xff0c;但是&#xff0c;唉~ 作为新的 UP 主满足粉丝的基本要求&#xff0c;才能获得更多的点赞呀~是吧。 关于“ Kafka 如何保证消息不丢失 ”这…

最新自动化测试面试题总结(答案+文档)

1、你做了几年的测试、自动化测试&#xff0c;说一下 selenium 的原理是什么&#xff1f; 我做了五年的测试&#xff0c;1年的自动化测试&#xff1b; selenium 它是用 http 协议来连接 webdriver &#xff0c;客户端可以使用 Java 或者 Python 各种编程语言来实现&#xff1…

Echarts图表柱状图x轴数据过多,堆叠处理

前言&#xff1a; 用echarts会遇到这种情况&#xff0c;以柱状图为例子&#xff0c;当数据过多时&#xff0c;echarts图就会堆叠在一起&#xff0c;看起来十分难看。通常是通过配置dataZoom来解决问题&#xff0c;但是这不是最佳的处理方案&#xff0c;我们可以根据柱状图X轴数…

使用代理IP保护爬虫访问隐私数据的方法探讨

目录 前言 1. 获取代理IP列表 2. 随机选择代理IP 3. 使用代理IP发送请求 4. 处理代理IP异常 总结 前言 保护爬虫访问隐私数据是一个重要的安全问题。为了保障用户的隐私&#xff0c;很多网站会采取限制措施&#xff0c;如封禁IP或限制访问频率。为了绕过这些限制&#x…