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

【算法】筛质数

news 来源：原创 2025/8/23 18:59:54

目录

  • 埃氏筛法
    • 算法原理
    • 代码
  • 欧拉筛法
    • 算法原理
    • 代码

埃氏筛法

算法原理

算法思想就像"筛子"一样，把合数筛掉，剩下的就是质数：

  1. 从2开始，依次检查每个数
  2. 如果当前数未被标记为合数，它就是质数
  3. 然后把这个质数的所有倍数都标记为合数
  4. 重复这个过程直到检查完所有数

注意：从i²开始标记：对于质数i，比i²小的倍数（如i×2, i×3,…, i×(i-1)）已经被更小的质数标记过了，所以可以从i²开始。
在这里插入图片描述

代码

#include <iostream>
using namespace std;typedef long long LL;
const int N = 1e6+10;
int check[N];     //真为合数 -- 被划掉的数
int prim[N];    //记录质数
int cnt = 0;        //质数个数void aishishai(int n)
{for(LL i = 2;i<=n;i++){//没被划掉if(!check[i]){prim[++cnt] = i;for(LL j = i*i;j<=n;j+=i)check[j] = 1;}}
}int main()
{int n;cin >> n;aishishai(n);cout << cnt;return 0;
}

欧拉筛法

算法原理

从小到大枚举每个数

  • 如果当前数没划掉，记录该质数
  • 枚举已经记录的质数（如果合数已越界则中断）
    • 合数未越界，则划掉合数
    • 条件i%p == 0，保证合数只被最小质因子划掉
      • 若i是质数，则最多枚举到自身中断
      • 若i是合数，则最多枚举到自身的最小质因子中断

在这里插入图片描述

代码

#include <iostream>
using namespace std;typedef long long LL;
const int N = 1e6+10;
int check[N];     //真为合数 -- 被划掉的数
int prim[N];    //记录质数
int cnt = 0;        //质数个数//欧拉筛
void get_prim(int n)
{for(int i  = 2;i<=n;i++){if(!check[i]) prim[++cnt] = i;for(int j =1;1ll * i*prim[j] <=n;j++) //越界中断{check[i*prim[j]] = 1;if(i%prim[j] == 0) break;//整除中断}}
}int main()
{int n;cin >> n;get_prim(n);cout << cnt;return 0;
}

相关文章：

【算法】筛质数

目录 埃氏筛法算法原理代码 欧拉筛法算法原理代码 埃氏筛法 算法原理 算法思想就像"筛子"一样&#xff0c;把合数筛掉&#xff0c;剩下的就是质数&#xff1a; 从2开始&#xff0c;依次检查每个数如果当前数未被标记为合数&#xff0c;它就是质数然后把这个质数的…...

编程日记 2025/8/23 18:59:54

【IDEA】✈️自定义模板，自动生成类和方法注释

&#x1f4a5;&#x1f4a5;✈️✈️欢迎阅读本文章❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;本篇文章阅读大约耗时三分钟。 ⛳️motto&#xff1a;不积跬步、无以千里 &#x1f4cb;&#x1f4cb;&#x1f4cb;本文目录如下&#xff1a;&#x1f381;&#x1f381;&a…...

编程日记 2025/8/23 18:58:24

笔试专题（六）

文章目录 最长无重复子数组&#xff08;滑动窗口&#xff09;题解代码 重排字符串&#xff08;贪心 构造&#xff09;题解代码 牛牛冲钻五&#xff08;模拟&#xff09;题解代码 最长无重复子数组&#xff08;滑动窗口&#xff09; 题目链接 题解 1. 滑动窗口 2. 什么时候…...

编程日记 2025/8/23 18:57:28

【算法实践】跳跃游戏——计算到达终点的最小跳数

问题描述 给定一个非负数数组 arr[]&#xff0c;每个元素表示从该位置最多可向前跳跃的步数。 示例&#xff1a; 若 arr[i] 3&#xff0c;则可以从位置 i 跳跃到 i1、i2 或 i3。若 arr[i] 0&#xff0c;则无法从该位置向前跳跃。 任务&#xff1a;找到从数组第一个位置移动…...

编程日记 2025/8/22 2:28:09

sklearn的Pipeline

Pipeline类 介绍：Pipeline 可以将多个数据处理步骤和机器学习模型组合成一个序列，其中每个步骤都是一个变换器（Transformer）或者估计器（Estimator），并且Pipeline中的最后一个必须为估计器，其它的必须为变换器，如果Pipeline中的估计器为为分类器则整个Pipeline就作为分…...

编程日记 2025/8/19 7:34:10

Unity3D仿星露谷物语开发34之单击Drop项目

1、目标 当在道具栏中选中一个Item时&#xff0c;点击地面就可以实现Item的drop操作&#xff0c;每点击一次就drop一次&#xff0c;直到道具栏中Item数量不够。 这样的好处&#xff1a;避免每次Drop都从道具栏中拖拉Item&#xff0c;通过点击这种操作可以更加高效。 方法&am…...

编程日记 2025/8/23 18:57:32

每日一题（小白）回溯篇4

深度优先搜索题&#xff1a;找到最长的路径&#xff0c;计算这样的路径有多少条&#xff08;使用回溯&#xff09; 分析题意可以得知&#xff0c;每次向前后左右走一步&#xff0c;直至走完16步就算一条走通路径。要求条件是不能超出4*4的范围&#xff0c;不能重复之前的路径。…...

编程日记 2025/8/23 18:58:24

Day16——路由2

路由独有的两个生命周期钩子 作用&#xff1a;用于捕获路由组件的激活状态 具体名字&#xff1a; activated 路由组件被激活时触发 deactivated 路由组件失活时触发 现在在缓存路由组件的基础上,想要使h2中的文字透明度不断变化&#xff0c;在切换到别的组件时销毁控制文字不…...

编程日记 2025/8/23 18:58:26

iproute2 工具集使用详解

目录 一、iproute2 核心命令&#xff1a;ip二、常用功能详解1. 管理网络接口&#xff08;link 对象&#xff09;2. 管理 IP 地址&#xff08;address 对象&#xff09;3. 管理路由表&#xff08;route 对象&#xff09;4. 管理 ARP 和邻居缓存&#xff08;neigh 对象&#xff0…...

编程日记 2025/8/19 20:04:22

C++学习之套接字并发服务器

目录 1.昨天套接字服务器的弊端 2.如何通过多进程方式实现服务器并发 3.多进程服务器-1 4.多进程服务器-2 5.多进程版程序-回收子进程被信号中断的处理 6.多线程版TCP服务处理思路 7.多线程并发服务器编写 8.为什么不能把文件描述符地址传到子线程中 9.多线程程序测试 …...

编程日记 2025/8/19 2:55:06

MCP项目开发-一个简单的RAG示例

MCP项目开发-一个简单的RAG示例 前言 前言 客户端是基于官网的例子改的&#xff0c;模型改成了openai库连接仅仅使用基础的RAG流程作为一个演示&#xff0c;包含了以下步骤 query改写搜索&#xff1a;使用google serper重排序&#xff1a;使用硅基流动的api 大模型api也使用…...

编程日记 2025/8/23 18:58:26

Windows安装ssh服务

使用管理员权限打开Windows PowerShell Add-WindowsCapability -Online -Name OpenSSH.Server~~~~0.0.1.0启动服务 Start-Service sshd 设置开机自启 Set-Service sshd -StartupType Automatic允许22端口 New-NetFirewallRule -Name “SSH” -DisplayName “SSH” -Enabled Tr…...

编程日记 2025/8/21 8:35:24

从零实现本地大模型RAG部署

1. RAG概念 RAG&#xff08;Retrieval-Augmented Generation&#xff09;即检索增强生成&#xff0c;是一种结合信息检索与大型语言模型&#xff08;大模型&#xff09;的技术。从外部知识库&#xff08;如文档、数据库或网页&#xff09;中实时检索相关信息&#xff0c;并将其…...

编程日记 2025/8/23 18:58:24

什么是ThreadLocal

ThreadLocal 是 Java 提供的一个工具类&#xff0c;它为每一个使用该变量的线程都提供了一个独立的变量副本。换句话说&#xff1a;每个线程都有自己的本地变量副本、互不干扰。它不是用来共享数据的&#xff0c;而是用来隔离数据的。 一、为什么需要 ThreadLocal&#xff1f;…...

编程日记 2025/8/23 18:58:25

MySQL-SQL-DQL语句、DQL基本查询、DQL条件查询、DQL分组查询、聚合函数、DQL排序查询、DQL分页查询

一. DQL DQL&#xff1a;Data Query Language(数据查询语言)&#xff0c;用来查询数据库表中的记录。 关键字&#xff1a;SELETE -- DQL 完整语法select字段列表 from表名列表 where条件列表 group by分组字段列表 having分组后条件列表 order by排序字段列表 limit分页参数 …...

编程日记 2025/8/20 22:10:44

vue2 vue3 响应式差异

vue2 响应式原理看这 链接: link 总结&#xff1a; object.defineproperty()是对属性的劫持&#xff0c;对属性劫持有两大缺陷 1. 需要遍历对象的所有属性&#xff0c;深层属性需递归&#xff0c;存在效率问题 2. 后添加的属性&#xff0c;无法获得响应式&#xff0c;因为劫持…...

编程日记 2025/8/23 18:57:30

常见NLP模型发展脉络：从传统方法到大语言模型

自然语言处理作为人工智能领域的重要分支&#xff0c;经历了从传统统计方法到深度学习的巨大飞跃。本文将带你梳理NLP模型的发展脉络&#xff0c;回顾那些推动技术进步的重要里程碑。 一、统计学习阶段&#xff08;1990s-2010s初&#xff09; 早期的NLP模型主要基于统计方法&…...

编程日记 2025/8/23 16:44:28

Bert论文解析

文章目录 BERT&#xff1a;用于语言理解的深度双向转换器的预训练一、摘要三、BERT介绍BERT及其详细实现答疑&#xff1a;为什么没有标注的数据可以用来预训练模型&#xff1f;1. 掩码语言模型&#xff08;Masked Language Model, MLM&#xff09;2. 下一句预测&#xff08;Nex…...

编程日记 2025/8/17 22:27:39

【数学】勒让德定理（legendres-formula）详解

勒让德定理&#xff08;Legendre’s Formula&#xff09;详解 这段代码使用的数学原理是勒让德定理&#xff0c;它是计算质数p在n!的质因数分解中指数的核心方法。 一、定理内容 对于任意质数p和正整数n&#xff0c;p在n!的质因数分解中的指数&#xff08;即n!能被p整除的最…...

编程日记 2025/8/22 5:12:23

时空联合规划算法

本文主要讲解时空时空联合规划算法。 文章目录 前言一、时空联合规划基本概念1.1 EM Planner算法求解过程1.2 时空联合规划算法求解过程二、基于搜索的规划方法2.1 构建三维时空联合规划地图2.2 基于Hybrid A*的时空联合规划二、基于迭代搜索的规划方法2.1 这段时间更新中2.2 这…...

编程日记 2025/8/23 18:57:30

如何在idea中新建一个项目

Java通常展现的方式就是项目&#xff0c;但是在不熟悉idea的情况下&#xff0c;我们应该如何创建一个项目呢&#xff1f; 第一步&#xff1a;点击File-->New-->Project 第二步&#xff1a;选择 Empty Project 第三步&#xff1a;点击File-->找到Project Structure--&…...

编程日记 2025/8/19 21:27:07

设计模式简述（十三）适配器模式

适配器模式 描述基本使用使用关于适配器关联不兼容类的方式如果原有抽象层是抽象类若原有抽象是接口使用 描述 适配器模式常用于系统已经上限稳定运行&#xff0c;但现有需求需要将两个不匹配的类放到一起工作时使用。 也就是说这是一个迭代阶段使用的模式。 这种模式&#x…...

编程日记 2025/8/23 18:58:27

功耗日志抓取需求

最近罗列了一些功耗分析需要的常见日志&#xff1a; 测试功耗前&#xff1a; adb shell dumpsys batterystats --reset adb shell dumpsys batterystats --enable full-wake-history 测试功耗后&#xff0c;使用脚本导出如下功耗日志&#xff1a; 脚本 chmod x collect_logs.s…...

编程日记 2025/8/23 18:57:29

设计模式简述（十一）装饰器模式

装饰器模式 描述基本使用使用 描述 装饰器模式是一种功能型模式 用于动态增强对象的功能 这么一说感觉上和代理模式有些类似 抽象装饰器 要实现原有业务接口&#xff0c;并注入原有业务对象 至于对原有业务对象的调用&#xff0c;可以采用private业务对象 实现业务接口方法的…...

编程日记 2025/8/23 18:58:24

MongoDB基础知识

MongoDB基础知识 目录 基础篇 一、MongoDB入门指南&#xff08;零基础必读&#xff09;二、MongoDB简介三、MongoDB安装与配置四、MongoDB基本操作五、MongoDB查询操作 进阶篇 六、MongoDB索引七、MongoDB聚合操作八、MongoDB数据模型九、MongoDB安全十、MongoDB备份恢复十一…...

编程日记 2025/8/22 12:56:29

Kubernetes详细教程（一）：入门、架构及基本概念

Kubernetes&#xff08;常简称为K8s&#xff09;是一个开源的平台&#xff0c;用于自动化部署、扩展和管理容器化应用程序。 官方文档&#xff1a;https://kubernetes.io/zh-cn/docs/concepts/overview/components/ 一、入门 &#xff08;一&#xff09;Kubernetes是什么&am…...

编程日记 2025/8/23 18:57:30

架构思维：限流技术深度解析

文章目录 Pre业务场景熔断 VS 限流4大限流算法固定时间窗口计数滑动时间窗口计数漏桶令牌桶 方案实现使用令牌桶还是漏桶模式&#xff1f;在 Nginx 中实现限流还是在网关层中实现限流&#xff1f;使用分布式限流还是单机限流&#xff1f;使用哪个开源技术&#xff1f; 限流方案…...

编程日记 2025/8/23 11:22:11

批量改CAD图层颜色——CAD c#二次开发

一个文件夹下大量图纸&#xff08;几百甚至几千个文件&#xff09;需要改图层颜色时&#xff0c;可采用插件实现&#xff0c;效果如下&#xff1a; 转换前&#xff1a; 转换后&#xff1a; 使用方式如下&#xff1a;netload加载此dll插件&#xff0c;输入xx运行。 附部分代码如…...

编程日记 2025/8/23 18:57:33

vue猜词游戏

说明&#xff1a;我希望用vue实现猜词游戏 Vue Wordle 游戏规则总结 ​核心规则 ​单词选择 目标单词从预设词库&#xff08;DEFAULT_WORDS&#xff09;中随机选取&#xff0c;均为5字母单词&#xff08;如apple、zebra等&#xff09;。 ​输入要求 ​长度限制&#xff1a;必须…...

编程日记 2025/8/21 3:27:52

SQL ②-库操作 | 数据类型

这里是Themberfue SQL语法 数据库术语 DATABASE&#xff1a;数据库&#xff0c;保存有组织的数据的容器&#xff08;通常是一个文件或一组文件&#xff09;。TABLE&#xff1a;表&#xff0c;某种特定类型数据的结构化清单。SCHEMA&#xff1a;模式&#xff0c;关于数据库和表…...

编程日记 2025/8/23 18:58:25

云轴科技ZStack CTO王为@中国GenAI大会：AI原生实践重构AI Infra新范式

4月1-2日&#xff0c;2025中国生成式AI大会&#xff08;GenAICon 2025&#xff09;在北京举办&#xff0c;该会议已成为国内AI领域最具影响力的产业峰会之一。来自学术界与产业界的50位嘉宾围绕GenAI应用、大模型、AI智能体、具身智能、DeepSeek R1与推理模型等话题&#xff0c…...

编程日记 2025/8/19 8:18:39

处理甘特图启动依赖报错。

处理甘特图启动报错 一、修改甘特图下载地址1.1 配置修改1.2 修改地址(https://registry.npmmirror.com) 二、安装依赖1.1 安装sass-loader1.2 适配安装dhtmlx-gantt 一、修改甘特图下载地址 1.1 配置修改 npm config get registry1.2 修改地址(https://registry.npmmirror.c…...

编程日记 2025/8/23 2:08:25

JSX、支持HTML标签、Ref的使用、虚拟DOM的使用

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》、《前端求职突破计划》 &#x1f35a; 蓝桥云课签约作者、…...

编程日记 2025/8/18 0:51:32

leetcode376-摆动序列

leetcode 376 思路 变量定义&#xff1a; prediff&#xff1a;记录上一次相邻元素的差值。用于判断当前差值与上一个差值的关系curdiff&#xff1a;记录当前相邻元素的差值result&#xff1a;记录当前的摆动序列的长度&#xff0c;初始化为 1&#xff0c;因为至少一个元素就…...

编程日记 2025/8/22 4:42:12

内网渗透(杂项集合) --- 中的多协议与漏洞利用技术(杂项知识点 重点) 持续更新

目录 1. NetBIOS 名称的网络协议在局域网中内网渗透中起到什么作用 2. 使用 UDP 端口耗尽技术强制所有 DNS 查找失败&#xff0c;这个技术如何应用在局域网内网渗透测试中 3. 在本地创建一个 HTTP 服务来伪造 WPAD 服务器 什么是 WPAD 服务器&#xff1f;这个服务器是干嘛的…...

编程日记 2025/8/22 8:27:32

14-产品经理-维护计划

产品经理的另一个职责是制定计划。古人云&#xff0c;凡事预则立&#xff0c;不预则废。 产品需要做规划&#xff0c;才能有轻重缓急&#xff0c;才能正确的做事。因此对于产品经理而言&#xff0c;计划是必需的。 对于产品经理自己而言&#xff0c;发布计划可以帮助他规划产…...

编程日记 2025/8/23 4:41:56

12-产品经理-维护模块

需求模块是帮助产品经理进行需求的分类和维护。 1. 维护模块 在具体产品的“研发需求”页面左侧&#xff0c;点击“维护模块”。也可以在具体产品的“设置”-“模块”下进行维护。 点击保存后&#xff0c;返回模块页面。还可以点击“子模块”对已有模块进行子模块的维护。 点击…...

编程日记 2025/8/21 22:28:24

解析HiveQL的ALTER TABLE ADD/REPLACE COLUMNS语句

阅读以下ALTER TABLE的ADD/REPLACE COLUMNS语句的语法&#xff0c;用C#编写解析函数&#xff0c;一个一个字符解析&#xff0c;所有关键字不区分大小写&#xff0c;一个或多个空格、Tab和换行的组合都可以是关键词之间的分隔&#xff0c;表名和字段名可能包含空格和Tab&#xf…...

编程日记 2025/8/21 16:12:16

MySQL-SQL-DML语句、INSER添加数据、UPDATE更新数据、DELETE删除数据

一. DML 1. DML的英文全称是Data Manipulation Language(数据操作语言)&#xff0c;用来对数据库中表的数据记录进行增、删、改操作。 2. 添加数据(INSERT)&#xff1b;修改数据(UPDATE)&#xff1b;删除数据(DELETE) 二. DML-INSER添加数据 -- DML insert -- 指定字段添加数…...

编程日记 2025/8/21 18:01:16

学透Spring Boot — 017. 处理静态文件

这是我的《学透Spring Boot》专栏的第17篇文章&#xff0c;了解更多内容请移步我的专栏&#xff1a; Postnull CSDN 学透 Spring Boot 目录 静态文件 静态文件的默认位置 通过配置文件配置路径 通过代码配置路径 静态文件的自动配置 总结 静态文件 以前的传统MVC的项目…...

编程日记 2025/8/17 23:27:04

Linux进程间通信——共享内存

1.概念 共享内存&#xff08;Shared Memory&#xff09;就是允许多个进程访问同一个内存空间&#xff0c;是在多个进程之间共享和传递数据最高效的方式。操作系统将不同进程之间共享内存安排为同一段物理内存&#xff0c;进程可以将共享内存连接到它们自己的地址空间中&#x…...

编程日记 2025/8/17 23:55:32

如何在大型项目中组织和管理 Vue 3 Hooks？

众所周知，Vue Hooks（通常指 Composition API 中的功能）是 Vue 3 引入的一种代码组织方式，用于更灵活地组合和复用逻辑。但是在项目中大量使用这种写法该如何更好的搭建结构呢？以下是可供参考实践的案例。 一、Hooks 组织原则 单一职责每个 Hook 应专注于完成单一功能，避…...

编程日记 2025/8/18 0:24:49

前后端开发的未来趋势

随着技术的不断进步，前后端开发模式也在不断演变。未来，微服务架构、Serverless、前后端融合（GraphQL、BFF）等趋势将深刻影响开发方式，使应用更高效、灵活、可扩展。 1. 微服务架构与 Serverless 1.1 微服务架构（Microservices Architecture） 微服务是一种软件架构模式…...

编程日记 2025/8/21 17:13:29

产品经理课程

原型工具 一、土耳其机器人 这个说法来源于 1770 年出现的一个骗局&#xff0c;一个叫沃尔夫冈冯肯佩伦&#xff08;Wolfgang von Kempelen&#xff09;的人为了取悦奥地利女皇玛丽娅特蕾莎&#xff08;Maria Theresia&#xff09;&#xff0c;“制造”了一个会下国际象棋的机…...

编程日记 2025/8/19 10:25:39

【开源宝藏】30天学会CSS - DAY12 第十二课 从左向右填充的文字标题动画

用伪元素搞定文字填充动效&#xff1a;一行 JS 不写&#xff0c;效果炸裂 你是否曾经在设计页面标题时&#xff0c;觉得纯文字太寡淡&#xff1f;或者想做一个有动感的文字特效&#xff0c;但又不想引入 JS 甚至 SVG&#xff1f; 在这篇文章中&#xff0c;我们将通过 一段不到…...

编程日记 2025/8/21 18:07:47

Nginx 负载均衡案例配置

负载均衡案例 基于 docker 进行 案例测试 1、创建三个 Nginx 实例 创建目录结构 为每个 Nginx 实例创建单独的目录&#xff0c;用于存储 HTML 文件和配置文件 mkdir -p data/nginx1/html mkdir -p data/nginx2/html mkdir -p data/nginx3/html添加自定义 HTML 文件 在每个…...

编程日记 2025/8/20 22:28:33

Golang系列 - 内存对齐

Golang系列-内存对齐 常见类型header的size大小内存对齐空结构体类型参考 摘要: 本文将围绕内存对齐展开, 包括字符串、数组、切片等类型header的size大小、内存对齐、空结构体类型的对齐等等内容. 关键词: Golang, 内存对齐, 字符串, 数组, 切片 常见类型header的size大小 首…...

编程日记 2025/8/20 22:46:28

nginx中的limit_req 和 limit_conn

在 Nginx 中&#xff0c;limit_req 和 limit_conn 是两个用于限制客户端请求的指令&#xff0c;它们分别用于限制请求速率和并发连接数。 limit_req limit_req 用于限制请求速率&#xff0c;防止客户端发送过多请求影响服务器性能。它通过 limit_req_zone 指令定义一个共享内存…...

编程日记 2025/8/20 18:19:31

Python Cookbook-5.4 根据对应值将键或索引排序

任务 需要统计不同元素出现的次数&#xff0c;并且根据它们的出现次数安排它们的顺序——比如&#xff0c;你想制作一个柱状图。 解决方案 柱状图&#xff0c;如果不考虑它在图形图像上的含义&#xff0c;实际上是基于各种不同元素(用Python的列表或字典很容易处理)出现的次…...

编程日记 2025/8/21 21:27:49

U535982 J-A 小梦的AB交换

U535982 J-A 小梦的AB交换 - 洛谷 题目描述 小梦有一个长度为 2⋅n 的 AB 串 s&#xff0c;即 s 中只包含 "A" 和 "B" 两种字符&#xff0c;且其中恰好有 n 个 "A" 和 n 个 "B"。 他可以对 s 执行以下操作&#xff1a; 选择 i,j (…...

编程日记 2025/8/23 1:24:46