1.2.2 Sum of Consecutive Prime Numbers

描述：一个正整数可以表示为一个或者多个连续素数的和。比如 53 有两种表示方法 53 和 5+7+11+13+17，但是 20 的 7+13 就不能满足条件，因为7和13并不是连续的素数。

输入：输入一个正整数序列，每个数一行，在2-10000之间取值。输入结束以0表示

输出：输出的每一行对应输入的每一行，除了最后的0.输出的每一行，对于一个输入的正整数，给出连续素数的和的表示法。输出中没有其他字符。

例如：

代码：

#include<iostream>
using namespace std;
const int maxp = 2000,n = 10000;   //设定数组表长和输入值的上限
int prime[maxp],total = 0;         //prime数组中默认都是0
bool isprime(int k)
{
    for(int i = 0;i<total;i++)
    {
        if(k%prime[i] == 0)        //素数的判断：一个数不能整除它之前的任何素数，那么它自己也是一个素数？？？
            return false;
    }
    return true;
}
int main()                          //主函数
{                                   //主函数开始
    for(int i = 2;i<=n;i++)         //预先建立素数表
        if(isprime(i))              //如果是素数，执行prime[total++]=i
            prime[total++]=i;       //将是素数的保存在prime数组中
    prime[total] = n+1;             
    
    int m;                           
    cin>>m;                          //输入第一个正整数
    while(m)                         //进入循环，直到输入正整数0为止
    {
        int ans = 0;                  //定义变量ans，用来记录m能被ans个素数相加得到
        for(int i=0;m>=prime[i];i++)  //外循环不断找出在m之前的素数
        {
            int cnt = 0;              //然后j从i开始，一直到j<total并且cnt<m,因为需要判断cnt与m是否相等
            for(int j = i;j<total&&cnt<m;j++)  //从j=0开始，prime[j]开始向后相加，判断。然后j=1开始，prime[j]向后相加再判断
                cnt+=prime[j];
            if(cnt==m)
                ++ans;
        }
        cout<<ans<<endl;
        cin>>m;
    }
    return 0;
}

分析：

1、 int prime[maxp] 这里开辟的一个2000的 int 类型的内存空间

2、素数的判断那里不是很明白？？？

3、外循环i：通过 for(int i = 0; m >= prime[i]; i++) 的循环结构枚举所有可能的最小素数prime[i]

内循环j：通过 for (int j = i; j < total&&cnt < m; j++) cnt += prime[j] 的循环结构计算连续素数的和cnt，内循环结束时cnt≥m。若cnt=m，则连续素数的和的表示数为ans+1，继续外循环

参考：《数据结构编程实验》吴永辉王建德编著

1.2.2 Sum of Consecutive Prime Numbers

相关推荐