当前位置：首页 > news >正文

【LeetCode每日一题】——204.计数质数

news 来源：原创 2025/5/13 7:04:13

文章目录

一【题目类别】
二【题目难度】
三【题目编号】
四【题目描述】
五【题目示例】
六【题目提示】
七【解题思路】
八【时空频度】
九【代码实现】
十【提交结果】

一【题目类别】

数组

二【题目难度】

中等

三【题目编号】

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^6$

七【解题思路】

该题如果使用暴力方法，那么很简单：
- 遍历每个数字
- 判断每个数字都否是质数
不过暴力方法的时间复杂度很高，本题的测试用例无法通过
暴力方法超时的原因在于需要逐一判断每个数字，所以我们对其进行优化，即采用埃拉托斯特尼筛法进行计算：
- 最开始我们假设所有数字都是质数
- 然后从2开始遍历到 $\sqrt{n}$
- 如果当前遍历到的数字为质数，那么设置其所有倍数都是质数
- 最后返回质数的数量即可
具体细节可以参考下面的代码

八【时空频度】

时间复杂度： $O (n l o g l o g n)$ ，其中 $n$ 为传入参数的值
空间复杂度： $O (n)$ ，其中 $n$ 为传入参数的值

九【代码实现】

Java语言版

class Solution {public int countPrimes(int n) {// 初始化时假设所有数字都是质数boolean[] isPrime = new boolean[n];// 使用埃拉托斯特尼筛法进行计算for (int i = 2; i < Math.sqrt(n); i++) {// 如果当前数字为质数，那么其所有倍数都是质数（注意范围不要超过给定值）if (isPrime[i] == false) {for (int j = i * i; j < n; j += i) {isPrime[j] = true;}}}// 最后筛选剩下的就是所有质数，计算其数量即可int count = 0;for (int i = 2; i < n; i++) {if (isPrime[i] == false) {count++;}}return count;}
}

Python语言版

class Solution:def countPrimes(self, n: int) -> int:# 初始化时假设所有数字都是质数is_prime = [True] * n# 使用埃拉托斯特尼筛法进行计算for i in range(2, int(n ** 0.5) + 1):# 如果当前数字为质数，那么其所有倍数都是质数（注意范围不要超过给定值）if is_prime[i]:for j in range(i * i, n, i):is_prime[j] = False# 最后筛选剩下的就是所有质数，计算其数量即可return sum(is_prime[2:])

C语言版

int countPrimes(int n)
{// 初始化时假设所有数字都是质数int* isPrime = (int*)calloc(n, sizeof(int));// 使用埃拉托斯特尼筛法进行计算for (int i = 2; i < sqrt(n); i++){// 如果当前数字为质数，那么其所有倍数都是质数（注意范围不要超过给定值）if (isPrime[i] == 0){for (int j = i * i; j < n; j += i){isPrime[j] = 1;}}}// 最后筛选剩下的就是所有质数，计算其数量即可int count = 0;for (int i = 2; i < n; i++){if (isPrime[i] == 0){count++;}}free(isPrime);return count;
}

十【提交结果】

Java语言版
Python语言版
C语言版

【LeetCode每日一题】——204.计数质数

文章目录一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时空频度】九【代码实现】十【提交结果】一【题目类别】数组二【题目难度】中等三【题目编号】 204.计数质数四【题目描述】给定整数 n &…...

编程日记 2025/5/13 7:04:13

TCP的“可靠性”（下）——三次握手四次挥手

目录建立连接（三次握手）为啥要进行握手？？意义何在？？常见面试题：为啥必须是三次握手？ 断开连接（四次挥手）三次握手和四次挥手的相同点和不同点连接过程中涉及…...

编程日记 2025/5/13 4:47:42

【笔记2-5】ESP32：freertos消息队列

主要参考b站宸芯IOT老师的视频，记录自己的笔记，老师讲的主要是linux环境，但配置过程实在太多问题，就直接用windows环境了，老师也有讲一些windows的操作，只要代码会写，操作都还好，开发…...

编程日记 2025/5/12 9:33:45

java操作doc(二)——java利用Aspose.Words动态创建自定义doc文档

有关java动态操作word文档，上一篇写了如何使用模板动态设置对于内容以及相关单元格的动态合并问题，详细请参看如下文档： java利用Aspose.Words操作Word动态模板文档并动态设置单元格合并这篇文档说说，如何利用Aspose.Words动态…...

编程日记 2025/5/12 9:33:44

计算机光电成像理论基础

一、透过散射介质成像 1.1 光在散射介质中传输光子携带物体信息并进行成像的过程是一个涉及光与物质相互作用的物理现象。这个过程可以分为几个步骤来理解： 1. **光的发射或反射**： - 自然界中的物体可以发射光（如太阳）&am…...

编程日记 2025/5/12 9:33:43

【Qt中实现屏幕录制】

在Qt中实现屏幕录制可以通过使用QScreen和QVideoEncoder类来完成。以下是一个简单的示例代码，演示如何捕获屏幕并将其保存为视频文件。请确保已经安装了Qt Multimedia模块，因为我们将使用其中的类来处理视频编码。下面是一个基本的实现步骤&#xff1a…...

编程日记 2025/5/12 9:33:42

repo仓库转移到自己本地的git服务器

前提条件：搭建好gitolite 以转移正点原子rk3568_linux工程为例子，将其转移到自己的git服务器。获取完整repo仓库将正点原子epo仓库sync出来 evanevan-X99:~/SRC/atk$ .repo/repo/repo sync -l -j10 evanevan-X99:~/SRC/atk$ .repo/repo/repo list -n…...

编程日记 2025/5/13 5:29:58

java操作文件(一)——java如何实现多文件打包压缩并下载

在实际开发项目过程中，文件下载是异常频繁的操作，但是多文件zip打包下载并非常见使用场景，本文介绍如何使用io流操作多文件实现压缩并下载。特别说明： 无需依赖任何第三方包或者拆件一、效果展示： 1.打包前文件列…...

编程日记 2025/5/13 4:47:42

Git仓库移除文件的暂存和修改

在使用Git进行版本控制时，有时需要移除文件的暂存状态或者撤销对文件的修改。根据不同的需求和场景，可以采取不同的命令来完成这些操作。下面将详细介绍如何在Git中移除文件的暂存以及撤销文件的修改。请注意，在执行这些命令之前&#xff0…...

编程日记 2025/5/12 8:48:39

Kube-Prometheus-Stack安装时初始化导入自定义Grafana dashboards

获取Grafana dashboards的JSON文件这里是获取已经编辑好的Grafana dashboards的JSON文件；以便内置到Kube-Prometheus-Stack的helm charts的安装zip文件中。编辑自定义dashboards JSON文件获取dashboards JSON文件模板其实Kube-Prometheus-Stack内部本身已经内…...

编程日记 2025/5/13 5:58:31

OpenCV高级-滤波与增强文章目录 OpenCV高级-滤波与增强1-OpenCV平滑滤波1. 均值滤波 (cv2.blur())2. 高斯滤波 (cv2.GaussianBlur())3. 中值滤波 (cv2.medianBlur())4. 双边滤波 (cv2.bilateralFilter())总结 2-OpenCV边缘检测1. Sobel算子 (cv2.Sobel())2. Canny边缘检测 (cv…...

编程日记 2025/5/13 6:52:45

taro小程序进入腾讯验证码

接入原因昨天突然晚上有人刷我们公司的登录发送短信接口，紧急将小程序的验证码校验更新上去了接下来就是我们的接入方法，其实很简单，不过有时候可能大家着急就没有仔细看文档，腾讯验证码文档微信小程序地址，注意这里…...

编程日记 2025/5/13 4:48:56

微信小程序怎么实现非tabbar页面显示tabbar，自定义组件实现

微信小程序没有发现可以实现非tabbar页面显示tabbar的方法，但是可以在tabbar页面当中隐藏tabbar，使用wx.hideTabBar()方法就可以实现，在非tabbar页面调用wx.showTabBar()方法却会显示失败，不能显示tabbar onLoad() {wx.showTabBar…...

编程日记 2025/5/13 6:01:58

001集—— 创建一个WPF项目 ——WPF应用程序入门 C#

本例为一个WPF应用（.NET FrameWork）。首先创建一个项目双击xaml文件双击xaml文件进入如下界面，开始编写代码。效果如下： 付代码： <Window x:Class"WpfDemoFW.MainWindow"xmlns"http://schema…...

编程日记 2025/5/11 17:25:55

【LeetCode: 316. 去除重复字母 + 栈 + 哈希表】

🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨ 🌲 作者简介：硕风和炜，…...

编程日记 2025/5/13 4:32:13

基于Python的Selenium详细教程

一、PyCharm安装配置Selenium 本文使用环境：windows11、Python 3.10.5、PyCharm 2022.1.3、Selenium 4.3.0 需要你懂的技术：Python、HTML、CSS、JavaScript 1.Seleium安装： 在PyCharm终端或window命令窗口输入以下命令 #查看已安装的Pytho…...

编程日记 2025/5/13 6:39:52

金仓KDTS迁移工具报错ERROR: 对访问方法 “btree“ 数据类型 unknown 没有默认的操作符表

ERROR: 对访问方法 "btree" 数据类型 unknown 没有默认的操作符表查看错误日志 com.kingbase8.util.KSQLException: ERROR: 对访问方法 "btree" 数据类型 unknown 没有默认的操作符表Hint: 你必须指定一个操作符表给索引或定义一个默认的操作符表给数据…...

编程日记 2025/5/13 4:50:11

前端开发入门指南Day 17：TypeScript高级类型（泛型，类型守卫，Partial＜T＞和 Required＜T＞等）

泛型：代码的"变色龙" 🦎 为什么需要泛型？ 想象一个快递员，每天要处理不同类型的包裹。如果为每种类型的包裹都写一套处理程序，那会很麻烦。泛型就像是一个"通用的包裹处理系统"，它能…...

编程日记 2025/5/13 5:29:58

数据链路层（四）---PPP协议的工作状态

1 PPP链路的初始化通过前面几章的学习，我们学了了PPP协议帧的格式以及组成，那么对于使用PPP协议的链路是怎么初始化的呢？ 当用户拨号上网接入到ISP后，就建立起了一条个人用户到ISP的物理链路。这时，用户向ISP发送一…...

编程日记 2025/5/13 5:06:31

EasyNVR中HTTP-FLV协议无法播放怎么解决？

在科技日新月异的今天，摄像头作为公共安全领域的重要一环，其技术的不断提升正显著地改变着社会的安全格局。从最初的简单监控到如今的高清智能分析，我们可以对特定区域进行实时监控和记录，为社会的安全稳定提供了强有力的保障。问…...

编程日记 2025/5/12 7:28:35

微服务监控prometheus+Grafana

目录 Prometheus 概述核心组件特点使用场景 Grafana 概述功能特点使用场景 PrometheusGrafana组合部署和配置一、准备工作二、部署Prometheus 三、部署Grafana 四、创建监控仪表盘五、验证和调优总结微服务监控是确保微服务架构稳定运行的关键环节…...

编程日记 2025/5/13 5:45:29

C++编程：模拟实现CyberRT的DataVisitor和DataDispatcher

文章目录 0. 引言1. 设计概要1.1 主要组件1.2 类关系图1.3 工作流程 2. 代码实现2.1. 定义数据结构2.2. 实现 DataVisitor2.3. 实现 DataDispatcher2.4. 实现 Receiver2.5. 实现具体的 DataVisitor2.6. 示例主程序2.7. 编译和运行 0. 引言使用 C 实现一个类似CyberRT 架构的 …...

编程日记 2025/5/13 4:38:39

TongRDS分布式内存数据缓存中间件

命令优势支持高达10亿级的数据缓冲，内存优化管理，避免GC性能劣化。高并发系统设计，可充分利用多CPU资源实现并行处理。数据采用key-value多索引方式存储，字段类型和长度可配置。支持多台服务并行运行，服务之间可互…...

编程日记 2025/5/12 11:26:16

银河麒麟v4/v10 Ubuntu上添加服务过程-以编译postgressql数据库为例

1 首先联网安装依赖 apt-get install build-essential zlib1g-dev libssl-dev libreadline-dev libxml2-dev python-setuptools 2 下载安装包下载地址：https://ftp.postgresql.org/pub/source/v16.3/postgresql-16.3.tar.gz 3 编译安装 mkdir -p /data/pgsql…...

编程日记 2025/5/13 5:23:42

电子商务人工智能指南 1/6 - 搜索、广告和发现

介绍 81% 的零售业高管表示， AI 至少在其组织中发挥了中等至完全的作用。然而，78% 的受访零售业高管表示，很难跟上不断发展的 AI 格局。近年来，电子商务团队加快了适应新客户偏好和创造卓越数字购物体验的需求。采用 AI 不再是一…...

编程日记 2025/5/13 5:43:16

JAVA面试基础(总结了很多)

最近帮整理了一份JAVA的面试基础，不过很基础后面还回继续更新。 java的专业技能 2.1 java的基础部分 2.1.1 简单讲一下java的跨平台原理由于各操作系统（windows,liunx等）支持的指令集，不是完全一致的。就会让我们的程序在不同的操…...

编程日记 2025/5/13 5:34:14

PPT怎样做的更加精美

目录 PPT怎样做的更加精美 3D的GIF图片 3维空间图编辑结果有明显的对比阅读高质量文献，采用他们的图 PPT怎样做的更加精美 3D的GIF图片 3维空间图结果有明显的对比...

编程日记 2025/5/13 5:48:59

postgresql与pgvector安装与使用

环境变量修改打开 .bashrc 文件进行编辑： vim ~/.bashrc在文件的末尾添加上面的环境变量配置 # 添加 PostgreSQL 可执行文件路径到系统 PATH export PATH/home/....../pg/postgresql-12.4/bin:$PATH# 设置 PostgreSQL 数据目录 export PGDATA/home/....../pg/pos…...

编程日记 2025/5/13 4:57:10

Tomcat，javaweb， servlet , springBoot

在server.xml里配置服务器 <scope>provided</scope>打包的时候，这个jar包不会被打进去，因为tomcat已将封装了这个jar包，没必要要这个...

编程日记 2025/5/13 5:08:47

vue 通过 image-conversion 实现图片压缩

简介 vue项目中，上传图片时如果图片很大，通过 image-conversion 压缩到指定大小 1. 安装依赖 npm i image-conversion --save2. 引用 import * as imageConversion from image-conversion3. 使用 const newFile new Promise((resolve) > {// 压…...

编程日记 2025/5/12 17:18:07

自由学习记录（27）

event委托在类内可完全修改 （前提为该event在类中的声明为public，外部可访问，然后外部访问的时候不能直接改） 下面这段代码是在类的内部访问事件 void ClearAllListeners() {MyEvent null; }event 修饰的委托字段在类内部没…...

编程日记 2025/5/5 15:17:23

MATLAB数学建模之画图汇总

MATLAB是一种强大的数学软件，广泛应用于工程计算、控制设计、信号处理等领域。在数学建模中，MATLAB的绘图功能可以帮助我们直观地展示数据和模型结果。 1. 二维数据曲线图 1.1 绘制二维曲线的基本函数 plot函数用于绘制二维平面上的线性坐标曲线图&am…...

编程日记 2025/5/11 16:13:18

UML箭线图的理解和实践

在软件开发的世界里，UML（统一建模语言）作为一种标准化的建模语言，扮演着举足轻重的角色。UML类图更是软件开发设计和架构过程中的核心工具，它不仅能帮助开发者明确系统中的类及其关系，还能为后续的代码实现…...

编程日记 2025/5/11 2:58:32

C#中的多态

多态（Polymorphism）是面向对象编程中的核心概念之一，它允许对象在不同的上下文中表现出不同的行为。简单来说，多态使得相同的方法调用可以表现出不同的行为，这使得代码更加灵活、可扩展和可维护。在 C# 中&#xff0…...

编程日记 2025/5/7 7:31:08

【SQL】实战--组合两个表

题目描述表: Person ---------------------- | 列名 | 类型 | ---------------------- | PersonId | int | | FirstName | varchar | | LastName | varchar | ---------------------- personId 是该表的主键（具有唯一值的列）…...

编程日记 2025/4/25 6:22:57

Unity 的介绍

Unity是一款功能强大的跨平台游戏开发引擎，以下是关于它的详细介绍： 一、概述 Unity由Unity Technologies公司开发，它提供了一个直观的开发环境，用于创建2D、3D游戏、模拟、虚拟现实（VR）、增强现实&#…...

编程日记 2025/5/10 23:54:00

深度学习的进展

深度学习新纪元引言你是否曾想过，为什么智能助手能理解你的指令，数字图像能够被准确分类，甚至疾病能被更早地诊断？这些现代奇迹背后都有一个共同的驱动力——深度学习。它不仅是当今人工智能领域的闪亮明星，更是一…...

编程日记 2025/5/9 17:37:07

vue中实现数字滚动效果

安装vue-count-to npm install vue-count-to引入 vue-count-to <template><div><count-to :start-val"startVal" :end-val"endVal" :duration"duration" :decimals"decimals" :separator"separator" :pref…...

编程日记 2025/5/12 22:36:02

Python的textwrap库：文本包装的艺术

目录一、初识textwrap 二、textwrap的核心函数 1. fill 2. wrap 3. dedent 4. indent 5. shorten 三、高级用法与技巧 1. 处理特殊字符 2. 自定义断行逻辑 3. 自定义缩进和前缀四、实战案例五、总结在Python编程中，处理文本是一项基础且常见的任务…...

编程日记 2025/5/6 15:33:48

linux 系列服务器高并发下ulimit优化文档

系统输入 ulimit -a 结果如下解除或提高 Linux 系统的最大进程数在高并发场景中，合理设置 Linux 系统的最大进程数对于提升服务器性能至关重要。以下是具体步骤： 临时修改 ulimit 设置可以通过 ulimit 命令临时调整当前会话的最大进程数。查看当前…...

编程日记 2025/5/7 17:14:03

Spring03——基于xml的Spring应用

Spring开发中主要对Bean的配置 Bean的常用配置一览如下： Xml配置方式功能描述<bean id"" class"">Bean的id和全限定名配置<bean name"">通过name设置Bean的别名，通过别名也能直接获取到Bean实例<bean sc…...

编程日记 2025/4/29 17:11:35

IDEA 鼠标悬浮显示方法注释 javaDoc 及配置遇到的问题

方法详情： 鼠标悬浮时的效果： 设置方法： File -> Settings -> Editor -> Code Editing -> Quick Documentation,勾选红框中的选项可能会遇到的问题： 如果不能选中，如下图把下图的位置的选中项取消掉选…...

编程日记 2025/5/8 15:26:06

openstack创建浮动IP全过程

1、创建外部网络，即是provider网络，有关provider网络的详细解释请参见我之前的文章openstack中的self-service和provider网络_openstack provider网络不能创建vlan吗-CSDN博客 network create --share --external --provider-physical-network physnet1…...

编程日记 2025/5/11 18:05:12

利用空闲主机进行Nmap隐匿扫描：IP伪造与空闲扫描技术

IP伪造与空闲扫描技术在网络安全领域，扫描和识别目标主机的开放端口是攻击者获取目标信息的重要手段。传统的扫描方法可能会暴露扫描者的真实IP地址，从而引起目标主机的警觉。然而，IP地址伪造是一种巧妙的方式，可以帮助攻击者在…...

编程日记 2025/5/13 5:07:24

vue聊天对话语音消息播放动态特效

vue2写法，vue3也能用，粘之即走： 示例： <template><div class"voice-hidden"><divclass"voice-play-chat":class"[className, { animate-stop: !isPlaying }]"><div class&q…...

编程日记 2025/5/12 14:41:15

流媒体之linux下离线部署FFmpeg 和 SRS

前言用户对网络做了限制，只能访问指定的网址，和没网没啥区别，导致无法连接外网，无法获取安装包，还有一些编译需要的开源工具用户需要用平台查看库房的海康摄像头实时监控，只能在库房里一台纯净的ubantu…...

编程日记 2025/5/8 8:06:53

C/C++内存管理

1. C/C内存分布我们先来看下面的一段代码和相关问题 const int a（此时an存放在栈上）char char2[] "abcd"（此时是在栈上创建5个char类型大小的数组，并让用常量字符串来初始化数组内的内容，*char2就是数组…...

编程日记 2025/5/9 18:56:11

xiaolin coding 图解 MySQL笔记——锁篇

1. 全局锁是怎么用的？ flush tables with read lock 执行以后，整个数据库就处于只读状态了，这时其他线程执行对数据的增删改操作（insert、delete、update）；对表结构的更改操作（alter table、dr…...

编程日记 2025/5/10 5:52:46

node.js实现分页和jwt鉴权机制

const express require(express); const jwt require(jsonwebtoken); const app express(); // 模拟数据库 const db { users: [ { id: 1, username: user1, email: user1example.com }, // ...更多用户 ], // ...其他数据模型 }; // 应用中间件 app.use(express.json…...

编程日记 2025/5/13 3:03:15