Sum of Different Primes-程序员宅基地

技术标签： ACM

Description

A positive integer may be expressed as a sum of different prime numbers (primes), in one way or another. Given two positive integersn andk, you should count the number of ways to expressn as a sum ofk different primes. Here, two ways are considered to be the same if they sum up the same set of the primes. For example, 8 can be expressed as 3 + 5 and 5 + 3 but the are not distinguished.

When n and k are 24 and 3 respectively, the answer is two because there are two sets {2, 3, 19} and {2, 5, 17} whose sums are equal to 24. There are not other sets of three primes that sum up to 24. Forn = 24 andk = 2, the answer is three, because there are three sets {5, 19}, {7, 17} and {11, 13}. Forn = 2 andk = 1, the answer is one, because there is only one set {2} whose sum is 2. Forn = 1 andk = 1, the answer is zero. As 1 is not a prime, you shouldn’t count {1}. Forn = 4 andk = 2, the answer is zero, because there are no sets of two different primes whose sums are 4.

Your job is to write a program that reports the number of such ways for the givenn andk.

Input

The input is a sequence of datasets followed by a line containing two zeros separated by a space. A dataset is a line containing two positive integersn andk separated by a space. You may assume thatn ≤ 1120 andk ≤ 14.

Output

The output should be composed of lines, each corresponding to an input dataset. An output line should contain one non-negative integer indicating the number of the ways forn andk specified in the corresponding dataset. You may assume that it is less than 2³¹.

Sample Input

Sample Output

#include<stdio.h>
#include<string.h>
/*内存使用比较大，状态设成3维的数组，dp[i][j][k]，取到第i个质数用了k个数凑成j的方案数*/
int dp[200][1121][15],primes[200],isPrime[1121];
int main(){
    int i,j,k,n,cal;
    memset(isPrime,1,sizeof(isPrime));
    cal=0;
    /*求出所有需要的素数*/
    for(i=2;i<1121;i++){
        if(isPrime[i]){
            primes[cal++]=i;
            for(j=2;j*i<1121;j++)
                isPrime[i*j]=0;
        }
    }
    /*dp----01背包*/
    dp[0][0][0]=1; 
    for(i=1;i<=cal;i++){
        for(j=0;j<1121;j++){
            for(k=0;k<15;k++){
                dp[i][j][k]=dp[i-1][j][k];
                if(primes[i-1]<=j&&k) 
                    dp[i][j][k]+=dp[i-1][j-primes[i-1]][k-1];
            }
        }
    }
    while(scanf("%d %d",&n,&k)&&(n||k))
        printf("%d\n",dp[cal][n][k]);
    return 0;
}

这是个01背包的问题，设计的状态是取到第I个质数用了k个数凑成j的方案数，上面的代码是三维数组，内存12560k,时间0ms下面进行对内存的优化...

下面的代码内存236KB，时间47ms...#include<stdio.h>
#include<string.h>
/*内存使用比较小，状态设成2维的数组*/
int dp[1121][15],primes[200],isPrime[1121];
int main(){
    int i,j,k,n,cal;
    memset(isPrime,1,sizeof(isPrime));
    cal=0;
    for(i=2;i<1121;i++){
        if(isPrime[i]){
            primes[cal++]=i;
            for(j=2;j*i<1121;j++)
                isPrime[i*j]=0;
        }
    }
    dp[0][0]=1;
    for(i=1;i<=cal;i++){
        for(j=1120;j>=0;j--){
            for(k=14;k>=0;k--){
                if(primes[i-1]<=j&&k)
                    dp[j][k]+=dp[j-primes[i-1]][k-1];
            }
        }
    }
    while(scanf("%d %d",&n,&k)&&(n||k))
        printf("%d\n",dp[n][k]);
    return 0;
}

本文链接：https://blog.csdn.net/qingboda110/article/details/51100673

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

nginx反向代理，request.getServerName()的问题_nginx request.getservername()-程序员宅基地

文章浏览阅读2.6k次。前几天配置了nginx的反向代理。可是有个问题。在项目中，写request.getServerName()的时候，总是返回的127.0.0.1 这个地址。折腾的好久，今天搜了搜，发现是配置的原因，记载一下。我以前的配置：[html] view plain copy location / { proxy_pass http://127.0.0.1:18..._nginx request.getservername()

如何使用Unity制作虚拟导览(一)_unity 商场导览程序-程序员宅基地

文章浏览阅读3.2k次，点赞3次，收藏12次。Unity用来制作游戏已经是目前市场上的一个发展趋势，而且有越来越多的公司与开发者不断的加入，那么Unity的应用是否能涵盖到各种领域?如果使用Unity制作建筑景观模拟？没错，这已是一个新时代的潮流，许多设计院的老板们发现，如果还是用效果图与一段动画展示已经很难满足客户的需求了，而公司内部现有的CAD软件与3dsmax能否与Unity完美搭配？是否需要其他的投入？我们来看看现在设计院的情_unity 商场导览程序

c# async await-程序员宅基地

文章浏览阅读8.1k次，点赞6次，收藏14次。本篇博客来谈一下我对c#中的async和awaite关键字的理解。先来聊聊我在理解这个异步编程机制时的困惑吧。我看了[使用 Async 和 Await 的异步编程（C# 和 Visual Basic）]这篇文章后，感觉so easy，异步方法返回一个Task对象，凭着我对Task类的“深入理解”，我就断定：当调用一个同步方法时，由于同步方法返回的是Task，.net自动就让这个ta

关于XML解析报错问题（LF、CRLF）-程序员宅基地

文章浏览阅读2.1k次。报错内容的主要部分：UnicodeDecodeError: ‘gbk’ codec can’t decode byte 0x80 in position123: illegal multibyte sequence问题产生在做目标检测时，使用的数据集来自网络，在将xml和图片转换到特定格式时，有些xml文件解析出现了问题。像这样：我发现，当我未使用labelImg工具，而直接通过记..._xml解析报错

C1083_qt 提升自定义控件 no such file or directory-程序员宅基地

文章浏览阅读145次。在使用QT过程中会自定义一些控件。比如：自定义了一个树形控件。使用的时候，在界面上拖动创建一个树形控件，然后使用“提升为”当前自定义的树形控件。提升之后的结果：但是编译的时候，出现了错误：\GeneratedFiles\ui_QtGuiUserDraw.h(23): fatal error C1083: 无法打开包括文件: “userdrawgeotree.h”: No such file or directory (编译源文件 QtGuiUserDraw.cpp)1。_qt 提升自定义控件 no such file or directory

java中所有的类都继承于_Java中所有的类都是通过直接或间接地继承( )类得到的...-程序员宅基地

文章浏览阅读4.2k次。Java中所有的类都是通过直接或间接地继承( )类得到的答：java.lang.Object关于主机地址 192.168.19.125 (子网掩码： 255.255.255.248 )，以下说法正确答：广播地址为：192.168.19.127 ；网络地址为：192.168.19.120 ；在小儿基本手法中，逆运内八卦的功效是?(??)答：宽胸利膈，行滞消食对事物的知觉是答：人脑对直接作用感官的..._java中所有的类都是通过直接或间接地继承( )类得到的。 2分 a、java.lang.object

随便推点

用python做一个数据查询软件_GitHub - lepfinder/dbmaster: 一个python实现的online SQL 查询器...-程序员宅基地

文章浏览阅读810次。介绍dbmaster是一个python编写的在线数据库查询客户端，可以有效隔离线上数据库环境，提供了一系列便于开发者使用的特性。操作体验尽量兼容navcat。github地址：https://github.com/lepfinder/dbmaster特性支持SQL语法高亮和自动提示支持SQL格式化支持执行选中的SQL片段支持数据库SCHEMA显示和表结构信息(双击表名显示表结构信息)支持快捷键执行..._dbmaster

利用Vultr主机安转宝塔Web面板搭建wordpress博客建站教程_vulrt 安装宝塔面板-程序员宅基地

文章浏览阅读924次。本篇文章是针对新手个人站长，来教大家利用Vultr主机如何安装宝塔Web面板搭建wordpress博客的方法。1、一台Vultr VPS主机，如果没有的可以购买（vultr官网），现在Vultr有活动，新用户注册送100美元，参考《Vultr优惠码汇总 Vultr优惠充值活动更新》。2、注册Vultr账号创建VPS实例创建VPS实例点击Deploy Now创建服务器实例，Status显示Running表示已经成功安装，一版需要等5-10分钟。IP Address:XX.XX.XXX.XXXU_vulrt 安装宝塔面板