当前位置: 首页 > java >正文

蓝桥杯2300 质数拆分

问题描述

将 2022 拆分成不同的质数的和,请问最多拆分成几个?

01背包问题

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;int prime[2025];
int dp[2025];  //dp[j]:和为 j 时的最多拆分质数个数//2022数较小,使用普通的质数判断函数 
bool is_prime(int x)
{if(x<2) return 0;if(x==2) return 1;for(int i=2; i<=sqrt(x); ++i){if(x%i==0) return 0;}return 1;
}int main()
{	int cnt=0;for(int i=2; i<=2022; ++i){if(is_prime(i)){cnt++;prime[cnt] = i;}}for(int i=1; i<=cnt; ++i){//倒序,避免重复使用同一个质数for(int j=2022; j>=prime[i]; j--){dp[j] = max(dp[j], dp[j-prime[i]] + 1);}}cout<<dp[2022];return 0;
} 
http://www.xdnf.cn/news/7378.html

相关文章:

  • 码蹄集——N是什么、棋盘
  • JVM(Java 虚拟机)深度解析
  • web基础常用标签
  • More Effective C++:改善编程与设计(下)
  • Seata源码—6.Seata AT模式的数据源代理三
  • 洛谷U536262 井底之“鸡” 附视频讲解
  • 提示词专家的修炼秘籍
  • harris角点检测
  • VisionPro:轴承错位标识
  • QT之绘图模块和双缓冲技术
  • MapStruct Date 转 LocalDate 偏差一天问题
  • 【C++】异常解析
  • AGI大模型(28):LangChain提示模板
  • MySQL中的Change Buffer是什么,它有什么作用?
  • 火山 RTC 引擎9 ----集成 appkey
  • 5月19日笔记
  • 4.7 时间模块
  • 网络传输(ping命令,wget命令,curl命令),端口
  • 接口排查不能靠猜:实战中如何用抓包工具精准定位问题(含 Charles 使用示例)
  • 人工智能、机器学习与深度学习:全面介绍与对比分析
  • 组态王通过开疆智能profinet转ModbusTCP网关连接西门子PLC配置案例
  • 队列和栈的区别
  • 【科研项目】大三保研人科研经历提升
  • Windows多功能工具箱软件推荐
  • gcc: attribute: packed
  • 区块链blog2_中心化与效率
  • 将 Element UI 表格拖动功能提取为公共方法
  • SpringBoot(二)--- SpringBoot基础(http协议、分层解耦)
  • HGDB中如何为表增加自增主键
  • 如何映射 MongoDB 的 _id 字段?