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

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

智能推荐

R语言单因素/多因素 Logistic回归_单因素logistic回归和多因素logistic回归r语言-程序员宅基地

文章浏览阅读1.1w次，点赞3次，收藏78次。变量因子的转换->单因素logistic回归->多因素logistic回归https://mp.weixin.qq.com/s/NowePGv6DF9_dF4blSyzVQ_单因素logistic回归和多因素logistic回归r语言

html 中的空格%3c br%3e,URL编码表一览 - frabbit的个人空间 - OSCHINA - 中文开源技术交流社区...-程序员宅基地

文章浏览阅读1w次。æ退格TAB换行回车空格!"#$%&'()*+,-./%00%01%02%03%04%05%06%07%08%09%0a%0b%0c%0d%0e%0f%10%11%12%13%14%15%16%17%18%19%1a%1b%1c%1d%1e%1f%20%21%22%23%24%25%26%27%28%29%2a%2b%2c%2d%2e%2f0123456789:;<=>?@AB..._html中%0d

运用js绘制SVG图片_nodejs绘制svg-程序员宅基地

文章浏览阅读2.7k次。/** * Create an element and draw a pie chart into it. * 创建一个元素，并在其中绘制一个饼状图 * Arguments: * 参数： * data: an array of numbers to chart, one for each wedge of the pie. * data：用于绘制数据的类型数_nodejs绘制svg

fatal error C1061: 编译器限制 : 块嵌套太深-程序员宅基地

文章浏览阅读7.2k次。VisualStudio开发过程中碰到C1061报错，查了MSDN，文档说明如下从说明中我们明白这是由于我们的代码块嵌套太深，超过了编译器的限制。但我理解为应该是同一个域内块的数量太多，超过了编译器限制。示例代码如下：void Demo1(){ for( int i = 0; i < 10; ++i ) { cout << i << " "; } cout <_块嵌套太深

《痞子衡嵌入式半月刊》第 36 期_gxepd2-程序员宅基地

文章浏览阅读489次。痞子衡嵌入式半月刊：第 36 期这里分享嵌入式领域有用有趣的项目/工具以及一些热点新闻，农历年分二十四节气，希望在每个交节之日准时发布一期。本期刊是开源项目(GitHub: JayHeng/pzh-mcu-bi-weekly)，欢迎提交 issue，投稿或推荐你知道的嵌入式那些事儿。上期回顾：《痞子衡嵌入式半月刊：第 35 期》唠两句这周四是大暑，历史上的今天：1991年7月2..._gxepd2

C#winform向cmd命令窗输入CTRL+C命令_c# winfrom 多线程加载cmd命令-程序员宅基地

文章浏览阅读8.6k次，点赞2次，收藏13次。最近在写一个很坑爹的工具，winform需要调用一个python写的工具。我的方法是直接开个线程调用System.Diagnostics.Process启动一个cmd窗，然后往里面p.StandardInput.WriteLine(python ...)相关指令： System.Diagnostics.Process p = new System.Diagnostics.Process()_c# winfrom 多线程加载cmd命令

随便推点

使用ASIHTTPRequest和ASIDownloadCache实现本地缓存-程序员宅基地

文章浏览阅读404次。为了节约流量，同时也是为了更好的用户体验，目前很多应用都使用本地缓存机制，其中以网易新闻的缓存功能最为出色。我自己的应用也想加入本地缓存的功能，于是我从网上查阅了相关的资料，发现总体上说有两种方法。一种是自己写缓存的处理，一种是采用ASIHTTPRequest中的ASIDownloadCache。根据我目前的技术水平和时间花费，我果断选择了后者，事实证明效果也很不错。下面说一下实现方法：

容器的end()方法-程序员宅基地

文章浏览阅读195次。容器的end()方法，返回一个迭代器，需要注意：这个迭代器不指向实际的元素，而是表示末端元素的下一个元素，这个迭代器起一个哨兵的作用，表示已经处理完所有的元素。因此，在查找的时候，返回的迭代器，不等于end()，说明找到了目标。等于end()，说明检查了所有元素，没有找到目标。转载于:https://www.cnblogs.com/nzbbody/p/3409317.html..._容器非实例化end

数据库（Database）介绍_数据库(database),简而言之可视为电子化的文件柜——存储电子文件的处所,用户可以-程序员宅基地

文章浏览阅读2.7k次。什么是数据库？数据库，简而言之可视为电子化的文件柜——存储电子文件的处所，用户可以对文件中的数据运行新增、截取、更新、删除等操作。所谓“数据库”系以一定方式储存在一起、能予多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。什么是数据库管理系统？数据库管理系统（英语：Database Management System，简称DBMS）是为管理数据库而设计的电脑软件系统，一般具有存储、截取、安全保障、备份等基础功能。数据库管理系统可以依据..._数据库(database),简而言之可视为电子化的文件柜——存储电子文件的处所,用户可以