JXFCZX — 质数和分解(完全背包)
发布日期:2021-07-01 00:18:44
浏览次数:3
分类:技术文章
本文共 952 字,大约阅读时间需要 3 分钟。
题目链接:
时间:1 秒 空间:512 MB问题描述
任何大于l的自然数n,都可以写成若干个大于等于2且小于等于n的质数之和的形式f(包括只有一个数构成的和表达式的情况),并且可能有不止一种质数和的形式。
例如9的质数和表达式就有四种本质不同的形式:9=2+5+2=2+3+2+2=3+3+3=2+7 。
这里所谓两个本质相同的表达式,是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。
试编程求解自然数n可以写成多少种本质不同的质数和的表达式。
输入格式
每一行存放一个自然数n(2≤n≤200)。
输出格式
输出自然数n的本质不同的质数和表达式的数目。
样例输入
2
200
样例输出
1
9845164
解题思路
先把素数筛出来,然后跑一遍完全背包就行了。
Accepted Code:#includeusing namespace std;int isprime[205], prime[205], dp[205];void is_prime(int n) { int k = 0; for (int i = 2; i <= n; i++) isprime[i] = 1; for (int i = 2; i <= n; i++) { if (isprime[i]) { prime[k++] = i; for (int j = i << 1; j <= n; j += i) isprime[j] = 0; } }}int main() { int n; scanf("%d", &n); dp[0] = 1; is_prime(n); for (int i = 0; prime[i] && prime[i] <= n; i++) for (int j = prime[i]; j <= n; j++) dp[j] += dp[j - prime[i]]; printf("%d\n", dp[n]); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/91039810 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月26日 17时28分44秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Android 之 ContentProvider 与 ContentResolver
2019-05-01
【接口自动化】
2019-05-01
Spring Boot 安全框架 Shiro 入门
2019-05-01
推荐一位川大零基础转行 Python 的人生勇士
2019-05-01
Python解惑之:True与False
2019-05-01
你要的微信小程序终于来了
2019-05-01
有了这些 Chrome 插件,效率提升10倍(建议收藏)
2019-05-01
Python 开发者都会遇到的错误:UnboundLocalError
2019-05-01
只有1%的程序员搞懂过浮点数陷阱
2019-05-01
一名 Google 工程师的大数据处理经验
2019-05-01
命名难,难于上青天
2019-05-01
史上最烂项目:苦撑12年,600多万行代码...
2019-05-01
没钱没公司,怎么做一款付费产品
2019-05-01
代码整洁之道-编写 Pythonic 代码
2019-05-01
树莓派程序开机自启动
2019-05-01
连锁门店无线通信方案
2019-05-01
配置Lotus Domino集群视频详解
2019-05-01
Linux软件万花筒
2019-05-01
全球开源软件发展趋势分析
2019-05-01