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

反素数c++

news 来源：原创 2025/7/15 19:43:22

先上代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n;

ll p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

int maxd,maxval;

void dfs(int pl,ll tmp,int num,int up){

if((num>maxd)||(num==maxd&&maxval>tmp)){

maxd=num;

maxval=tmp;

}

if(pl==16) return;

for(int i=1;i<=up;i++){

if(tmp*p[pl]>n) return;

tmp*=p[pl];

dfs(pl+1,tmp,num*(i+1),i);

}

int main(){

cin>>n;

dfs(0,1,1,63);

cout<<maxval<<endl;

return 0;

}

代码解析：寻找不超过n的反素数

这段代码是用来寻找不超过给定正整数n的反素数（antiprime number）。反素数是指在一个特定范围内拥有最多因数的数中最小的那个。

反素数的定义和性质

反素数具有以下性质：

它是范围内因数个数最多的数
如果有多个数具有相同的最大因数个数，则选择其中最小的一个
反素数的质因数分解中，质数是从小到大排列的，且指数是单调不增的

代码结构分析

1. 全局变量和预处理

typedef long long ll;
ll n;
ll p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int maxd, maxval;

p[]数组存储了前16个质数（2到53）
maxd记录当前找到的最大因数个数
maxval记录对应的数值

2. 深度优先搜索函数dfs

void dfs(int pl, ll tmp, int num, int up) {if((num>maxd)||(num==maxd&&maxval>tmp)) {maxd = num;maxval = tmp;}if(pl == 16) return;for(int i=1; i<=up; i++) {if(tmp*p[pl] > n) return;tmp *= p[pl];dfs(pl+1, tmp, num*(i+1), i);}
}

参数说明：

pl：当前考虑的质数在p[]中的索引
tmp：当前生成的数值
num：当前数值的因数个数
up：当前质数的最大可能指数（保证指数单调不增）

函数逻辑：

检查当前数值是否比已记录的最优解更好（因数更多，或因数相同但数值更小）
如果已经考虑完所有质数（16个），则返回
尝试为当前质数分配指数i（从1到up）
- 确保乘积不超过n
- 递归处理下一个质数，更新数值、因数个数，并限制下一个质数的指数不超过当前i

3. 主函数

cpp

复制

下载

int main() {cin >> n;dfs(0, 1, 1, 63);cout << maxval << endl;return 0;
}

读取输入的n
从第一个质数（索引0）开始搜索，初始数值为1，因数个数为1，初始指数上限设为63（足够大）
输出找到的反素数

算法原理

因数个数计算：一个数的因数个数等于其质因数分解各指数加1的乘积。例如，12=2²×3¹，因数个数为(2+1)×(1+1)=6。
贪心策略：为了找到因数最多且数值最小的数，我们：
- 优先使用较小的质数
- 确保质数的指数是单调不增的（更大的质数指数不超过前面的）
剪枝优化：
- 当当前乘积超过n时停止继续尝试
- 限制后续质数的指数不超过前一个质数的指数

示例分析

假设n=10：

搜索过程会尝试以下组合：
- 2^1 = 2 (因数2)
- 2^2 = 4 (因数3)
- 2^3 = 8 (因数4)
- 3^1 = 3 (因数2)
- 2^1×3^1 = 6 (因数4)
- 其他组合会超过10
最终找到6和8都有4个因数，选择较小的6

复杂度分析

时间复杂度：O(2^k)，其中k是质数个数（这里k=16），但由于剪枝和指数限制，实际运行很快
空间复杂度：O(k)递归深度

这段代码高效地利用了反素数的数学性质和DFS剪枝策略，能够在合理时间内找到不超过n的最大反素数。

进行递归时要注意手动模拟理解代码，例如n=18时，一次进行这样的搜索

1. 2^1 (因数2)

2. 2^1*3^1（因数4）

3. 2^2 （因数3）

4. 2^2*3^1（因数6）

5. 2^3 （因数4）

如此得到答案12

自己这样模拟一遍便能理解代码是如何操作并进行筛选出最终答案了

反素数c++

先上代码 #include<bits/stdc.h> using namespace std; typedef long long ll; ll n; ll p[]{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; int maxd,maxval; void dfs(int pl,ll tmp,int num,int up){ if((num>maxd)||(nummaxd&&maxval>tmp)){ …...

编程日记 2025/7/15 19:43:22

C++ linux打包运行方案（cmake）

文章目录背景动态库打包方案动态库转静态库动态库打到软件包中运行背景使用C编写的一个小项目，需要打包成ubuntu下的可执行文件，方便分发给其他ubuntu执行，因为docker镜像方案过于臃肿，所以需要把项目的动态库都打在软件包中…...

编程日记 2025/7/14 7:25:47

JavaScript 渲染内容爬取实践：Puppeteer 进阶技巧

进一步探讨如何使用 Puppeteer 进行动态网页爬取，特别是如何等待页面元素加载完成、处理无限滚动加载、单页应用的路由变化以及监听接口等常见场景。一、等待页面元素加载完成在爬取动态网页时，确保页面元素完全加载是获取完整数据的关键。Puppeteer…...

编程日记 2025/7/15 0:12:41

AI数字人：元宇宙舞台上的闪耀新星（7/10）

摘要：AI数字人作为元宇宙核心角色，提升交互体验，推动内容生产变革，助力产业数字化转型。其应用场景涵盖虚拟社交、智能客服、教育、商业营销等，面临技术瓶颈与行业规范缺失等挑战，未来有望突破技术限制&…...

编程日记 2025/6/29 10:56:09

测试基础笔记第九天

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录一、数据类型和约束1.数据类型2.约束3.主键4.不为空5.唯一6.默认值二、数据库操作1.创建数据库2.使用数据库3.修改数据库4.删除数据库和查看所有数据库5.重点&…...

编程日记 2025/7/13 20:01:50

C++抽象基类定义与使用

在 C 中，抽象基类（Abstract Base Class, ABC） 是一种特殊的类，用于定义接口规范和约束派生类的行为。它通过纯虚函数（Pure Virtual Function）强制要求派生类实现特定功能，自身不能被实例化。以下…...

编程日记 2025/7/15 19:41:36

20.4 显示数据库数据

编程日记 2025/7/15 1:37:29

PyTorch 多 GPU 入门：深入解析 nn.DataParallel 的工作原理与局限

当你发现单个 GPU 已经无法满足你训练庞大模型或处理海量数据的需求时，利用多 GPU 进行并行训练就成了自然的选择。PyTorch 提供了几种实现方式，其中 torch.nn.DataParallel (简称 DP) 因其使用的便捷性，常常是初学者接触多 GPU 训练的第一站…...

编程日记 2025/7/15 18:54:13

UDP协议理解

文章目录 UDP协议理解UDP 协议的特点：UDP协议图示UDP 的头部结构：UDP数据传输图示 UDP 的应用场景：TCP 与UDP对比UDP的传输丢包和顺序错乱问题（了解）丢包的解决方法：顺序错乱的解决方法：综合应用…...

编程日记 2025/7/13 12:15:29

微信小程序拖拽排序有效果图

效果图 .wxml <view class"container" style"--w:{{w}}px;" wx:if"{{location.length}}"><view class"container-item" wx:for"{{list}}" wx:key"index" data-index"{{index}}"style"--…...

编程日记 2025/6/29 9:31:44

算力网络的早期有关论文——自用笔记

2023年底至2024年初阅读有关论文的自用笔记，作为参考。算力网络架构 https://baijiahao.baidu.com/s?id1727377583404975414&wfrspider&forpc think&note 是否可以和cpu进程调度联系。目前：看一些综述深一步了解背景和发展现状,完善认…...

编程日记 2025/7/13 16:44:24

卷积神经网络基础（四）

今天我们继续学习各个激活函数层的实现过程。目录 5.2 Sigmoid层六、Affine/Softmax层实现 6.1 Affine层 6.2 批处理版本 5.2 Sigmoid层 sigmoid函数的表达式如下： 用计算图表示的话如下： 计算过程稍微有些复杂，且这里除了乘法和加法…...

编程日记 2025/6/29 9:31:25

【MySQL数据库】表的约束

目录 1，空属性 2，默认值 3，列描述 4，zerofill 5，主键primary key 6，自增长auto_increment 7，唯一键unique 8，外键foreign key 在MySQL中，表的约束是指用于插入的…...

编程日记 2025/7/13 17:01:43

网络威胁情报 | Friday Overtime Trooper

本文将分别从两个环境出发，以实践来体验利用威胁情报分析可疑文件的过程。 Friday Overtime 现在你是一位安全分析人员，正在美美等待周五过去，但就在即将下班之时意外发生了：你的客户发来求助，说他们发现了一些可疑文…...

编程日记 2025/7/13 20:16:19

GPIO（通用输入输出端口）详细介绍

一、基本概念 GPIO（General - Purpose Input/Output）即通用输入输出端口，是微控制器（如 STM32 系列）中非常重要的一个外设。它是一种软件可编程的引脚，用户能够通过编程来控制这些引脚的输入或输出状态。在…...

编程日记 2025/6/29 9:32:01

学习笔记——《Java面向对象程序设计》-继承

参考教材： Java面向对象程序设计（第3版）微课视频版清华大学出版社 1、定义子类 class 子类名 extends 父类名{...... }如： class Student extends People{...... } （1）如果一个类的声明中没有extends关…...

编程日记 2025/7/15 15:13:38

基于javaweb的SpringBoot校园失物招领系统设计与实现(源码+文档+部署讲解）

技术范围：SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。主要内容：免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论文…...

编程日记 2025/6/29 11:39:08

什么事Nginx，及使用Nginx部署vue项目（非服务器Nginx压缩包版）

什么是 Nginx？ Nginx（发音为 “engine-x”）是一个高性能的 HTTP 和反向代理服务器，也是一个 IMAP/POP3/SMTP 代理服务器。它以其高性能、高并发处理能力和低资源消耗而闻名。以下是 Nginx 的主要特性和用途：主要特性高性能和高并发 Nginx 能够处理大量并发连接，适合高…...

编程日记 2025/7/14 5:10:14

nodejs使用require导入npm包，开发依赖和生产依赖，全局安装

nodejs使用require导入npm包，开发依赖和生产依赖 ，全局安装 ✅ 一、Node.js 中使用 require() 导入 npm 包 // 导入第三方包（例如 axios） const axios require(axios);// 使用 axios.get(https://api.example.com).then(res &g…...

编程日记 2025/7/13 12:15:51

CSS在线格式化 - 加菲工具

CSS在线格式化打开网站加菲工具选择“CSS在线格式化” 或者直接访问 https://www.orcc.top/tools/css 输入CSS代码，点击左上角的“格式化”按钮得到格式化后的结果...

编程日记 2025/6/29 11:56:31

图片转base64 - 加菲工具 - 在线转换

图片转base64 - 加菲工具先进入“加菲工具” 网打开 https://www.orcc.top， 选择 “图片转base64”功能选择需要转换的图片复制点击“复制”按钮，即可复制转换好的base64编码数据，可以直接用于img标签。...

编程日记 2025/7/15 7:27:23

性能比拼: Redis vs Dragonfly

本内容是对知名性能评测博主 Anton Putra Redis vs Dragonfly Performance (Latency - Throughput - Saturation) 内容的翻译与整理, 有适当删减, 相关指标和结论以原作为准在本视频中，我们将对比 Redis 和 Dragonfly。我们将观察 set 与 get 操作的延迟&#xff…...

编程日记 2025/6/29 10:42:57

如何收集用户白屏/长时间无响应/接口超时问题

想象一下这样的场景：一位用户在午休时间打开某电商应用，准备购买一件心仪已久的商品。然而，页面加载了数秒后依然是一片空白，或者点击“加入购物车”按钮后没有任何反馈，甚至在结算时接口超时导致订单失败。用户的耐心被迅速消耗殆尽，关闭应用，转而选择了竞争对手的产品…...

编程日记 2025/6/29 11:00:35

来啦，烫，查询达梦表占用空间

想象一下oracle，可以查dba_segments，但是这个不可靠（达梦官方连说明书都没有） 先拼接一个sql set lineshow off SELECT SELECT ||||OWNER|||| AS OWNER,||||TABLE_NAME|||| AS TABLE_NAME,TABLE_USED_SPACE(||||OWNER||||,||||T…...

编程日记 2025/7/15 9:44:30

# 利用迁移学习优化食物分类模型：基于ResNet18的实践

利用迁移学习优化食物分类模型：基于ResNet18的实践在深度学习的众多应用中，图像分类一直是一个热门且具有挑战性的领域。随着研究的深入，我们发现利用预训练模型进行迁移学习是一种非常有效的策略，可以显著提高模型的性能&#…...

编程日记 2025/7/13 16:26:24

AT24C02芯片简介：小巧强大的串行EEPROM存储器

一、AT24C02概述 AT24C02是一款2K位（即256字节）的串行EEPROM芯片，采用IC（Inter-Integrated Circuit）总线进行通信，适合低功耗、小容量存储需求。主要特性： 项目参数存储容量 2Kb&#x…...

编程日记 2025/7/15 12:51:38

【Vue】状态管理（Vuex、Pinia）

个人主页：Guiat 归属专栏：Vue 文章目录 1. 状态管理概述1.1 什么是状态管理1.2 为什么需要状态管理 2. Vuex基础2.1 Vuex核心概念2.1.1 State2.1.2 Getters2.1.3 Mutations2.1.4 Actions2.1.5 Modules 2.2 Vuex辅助函数2.2.1 mapState2.2.2 mapGetters2.…...

编程日记 2025/6/29 11:50:20

施磊老师基于muduo网络库的集群聊天服务器(四)

文章目录实现登录业务登录业务代码补全数据库接口:查询,更新状态注意学习一下里面用到的数据库api测试与问题**问题1:****问题2:** 用户连接信息与线程安全聊天服务器是长连接服务器如何找到用户B的连接？在业务层存储用户的连接信息多线程安全问题加锁! 处理客户端…...

编程日记 2025/7/15 12:51:17

深度学习-全连接神经网络（过拟合，欠拟合。批量标准化）

七、过拟合与欠拟合在训练深层神经网络时，由于模型参数较多，在数据量不足时很容易过拟合。而正则化技术主要就是用于防止过拟合，提升模型的泛化能力(对新数据表现良好)和鲁棒性（对异常数据表现良好）。 1. 概念认知 …...

编程日记 2025/7/14 17:21:15

访问Maven私服的教程

1.首先准备好maven私服的启动器，到bin目录下启动： 2.等待加载，加载过程比较长: 3.访问端口号: 4.仓库简介: 5.在maven的setting中 servers配置信息(设置私服访问的密码): 6.配置私服仓库地址: 7.配置上传地址(私服地址): 8.在自己的副项…...

编程日记 2025/7/14 21:03:06

Linux系统编程 day9 SIGCHLD and 线程

SIGCHLD信号只要子进程信号发生改变，就会产生SIGCHLD信号。借助SIGCHLD信号回收子进程回收子进程只跟父进程有关。如果不使用循环回收多个子进程，会产生多个僵尸进程，原因是因为这个信号不会循环等待。 #include<stdio.h> #incl…...

编程日记 2025/7/9 13:30:15

Linux 内核中 cgroup 子系统 cpuset 是什么？

cpuset 是 Linux 内核中 cgroup（控制组） 的一个子系统，用于将一组进程（或任务）绑定到特定的 CPU 核心和内存节点（NUMA 节点）上运行。它通过限制进程的 CPU 和内存资源的使用范围，优…...

编程日记 2025/7/8 17:45:14

乐视系列玩机---乐视2 x520 x528等系列线刷救砖以及刷写第三方twrp 卡刷第三方固件步骤解析

乐视2 x520 x528 x526等，搭载了高通骁龙652处理器，骁龙652的GPU性能甚至优于前一年的骁龙810，配备了3GB RAM和32GB ROM的存储空间，通过博文了解💝💝💝 1💝💝💝-----详细解析乐视2 x520系列黑砖线刷救砖的步骤 2💝💝💝----官方两种更新卡刷步骤以及刷…...

编程日记 2025/7/11 23:15:15

电容加速电路！

大家好，我是记得诚。今天分享一个小电路：电容加速电路。下面是一个普通的三极管开关电路，区别是多了一个C1，C1被称为加速电容。作用是：加速三极管VT1的开通和截止，做到快开快关。工作原理：…...

编程日记 2025/7/14 19:58:23

MCP Host、MCP Client、MCP Server全流程实战

目录准备工作 MCP Server 实现调试工作 MCP Client 实现 MCP Host 配置第一步：配置支持 function calling的 LLM 第二步：添加MCP Server 一般有两种方式，第一种json配置，第二种直接是Command形式，我这里采用Command形式第三步：使用MCP Server 准备工作安装…...

编程日记 2025/6/29 11:36:17

Win10一体机（MES电脑设置上电自动开机）

找个键盘，带线的那种，插到电脑上，电脑开机；连续点按F11；通过↑↓键选择Enter Setup 然后回车； 选择 smart settings ； 选择 Restore AC Power Loss By IO 回车； 将prower off 改为…...

编程日记 2025/6/29 9:30:55

强化学习和微调区别如下

强化学习和微调区别如下定义与概念强化学习**：是一种机器学习范式，强调智能体（agent）如何在环境中采取一系列行动，以最大化累积奖励**。智能体通过与环境进行交互，根据环境反馈的奖励信号来学习最优的行为策略。例如，机器人通过不断尝试不同的动作来学习如何在复杂环…...

编程日记 2025/6/29 9:31:17

【EasyPan】文件上传、文件秒传、文件转码、文件合并、异步转码、视频切割分析

【EasyPan】项目常见问题解答（自用&持续更新中…）汇总版文件上传方法解析一、方法总览 Transactional(rollbackFor Exception.class) public UploadResultDto uploadFile(...)核心能力： 秒传验证：通过MD5文件大小实现文…...

编程日记 2025/6/29 9:31:23

React18+ 项目搭建-从初始化、技术选型到开发部署的全流程规划

搭建一个 React 项目需要从项目初始化、技术选型到开发部署的全流程规划。以下是详细步骤和推荐的技术栈： 一、项目初始化 1. 选择脚手架工具推荐工具： Vite（现代轻量级工具，支持 React 模板，速度快）&am…...

编程日记 2025/7/13 20:20:41

day3 打卡训练营

循环语句和判断语句之前已经会了，把列表的方法练一练浙大疏锦行 python训练营介绍...

编程日记 2025/7/15 1:37:46

MySQL VS SQL Server：优缺点全解析

数据库选型、企业协作、技术生态、云数据库 1.1 MySQL优缺点分析优点开源免费社区版完全免费，适合预算有限的企业允许修改源码定制功能（需遵守GPL协议） 跨平台兼容性支持Windows/Linux/macOS，适配混合环境部署云服务商…...

编程日记 2025/7/15 12:24:39

【CPP】固定大小内存池

程序运行时，通常会频繁地进行内存的分配和释放操作。传统的内存分配方式（如使用new和delete运算符）可能会导致内存碎片的产生，并且每次分配和释放内存都有一定的时间开销。内存池通过在程序启动时一次性分配一大块内存或一次性分配…...

编程日记 2025/7/15 9:45:05

[数据结构]树和二叉树

概念树是一种非线性的数据结构，它是由 n （ n>0 ）个有限结点组成一个具有层次关系的集合。树形结构中，子树之间不能有交集，否则就不是树形结构双亲结点或父结点 ：若一个结点含有子结点，则…...

编程日记 2025/7/14 17:25:16

监控页面卡顿PerformanceObserver

监控页面卡顿PerformanceObserver 性能观察器掘金 const observer new PerformanceObserver((list) > {}); observer.observe({entryTypes: [longtask], })...

编程日记 2025/6/29 11:45:19

Web开发-JavaEE应用JNDI注入RMI服务LDAP服务DNS服务高版本限制绕过

知识点： 1、安全开发-JavaEE-JNDI注入-LADP&RMI&DNS等 2、安全开发-JavaEE-JNDI注入-项目工具&手工原理等演示案例-WEB开发-JavaEE-JNDI注入&LDAP&RMI服务&DNS服务&高版本限制绕过 JNDI全称为 Java Naming and DirectoryInterface&am…...

编程日记 2025/7/6 4:04:02