算法思想,搜索+较强减枝.
小于5000的数据,可于瞬间出解,且保证解的准确性,若无解则输出No answer

/*
Author: SunKai
E-mail: sunkai [at] msn [dot] com
*/

#include<stdio.h>
#include<math.h>
#include<string.h>
#define SIZE 1000
int best[SIZE],lenbest; /*当前最好的序列及长度*/
int q[SIZE]; /*当前尝试*/ 
int x[SIZE]={2},lenx; /*质数表*/ 
int lenmax;
int dfs(int now,int left,int count)
{
    int i,j;
    int tmp;
    if(left==0)
    {
      if(count>lenbest)
      {
        memcpy(best,q,sizeof(best));
        lenbest=count;
      }
      if(count==lenmax) return 1;
      return 0;
    }
    for(i=now;i<lenx;i++)
    {
      if(left<x[i]) return 0;
      tmp=left;
      for(j=i;j<lenx;j++)
      {
        tmp-=x[j];
        if(tmp<0) break;
      }
      if(count+j-i<=lenbest) return 0;
      q[count]=x[i]; if(dfs(i+1,left-x[i],count+1)) return 1;
    }
    return 0;
}
int main(void)
{
    int i,j,tmp;
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        lenx=1;
        memset(best,0,sizeof(best));
        lenbest=0;
        for(i=3;i<=n;i++)
        {
          tmp=sqrt(i);
          for(j=2;j<=tmp;j++)
            if(i%j==0) break;
          if(j>tmp)
          {
            x[lenx]=i;
            lenx++;
          }
        }
        tmp=0; lenmax=0;
        for(i=0;i<lenx;i++)
        {
          tmp+=x[i];
          lenmax++;
          if(tmp>n) { lenmax--; break; }
          if(tmp==n) break;
        }
        dfs(0,n,0);
        for(i=0;i<lenbest;i++) printf("%4d ",best[i]);
        if(!lenbest) printf("No answer");
        printf("\n");
    }
    return 0;
}
    
    

程序二,经过本帖在11楼前的讨论,对于程序进行了修改,使之解为元素个数最多且最大元素最小

#include<stdio.h>
#include<math.h>
#include<string.h>
#define SIZE 1000
int best[SIZE],lenbest,great; /*当前最好的序列及长度*/
int q[SIZE]; /*当前尝试*/ 
int x[SIZE]={2},lenx; /*质数表*/ 
int lenmax;
int dfs(int now,int left,int count)
{
    int i,j;
    int tmp;
    if(left==0)
    {
      if(count>lenbest || (count==lenbest && q[count-1]<great))
      {
        memcpy(best,q,sizeof(best));
        lenbest=count;
        great=q[count-1];
      }
      if(count==lenmax) return 0;
      return 0;
    }
    for(i=now;i<lenx;i++)
    {
      if(left<x[i]) return 0;
      tmp=left;
      if(x[i]>great) return 0;
      for(j=i;j<lenx;j++)
      {
        tmp-=x[j];
        if(tmp<0) break;
      }
      if(count+j-i+1<=lenbest) return 0;
      q[count]=x[i]; dfs(i+1,left-x[i],count+1);
    }
    return 0;
}
int main(void)
{
    int i,j,tmp;
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        lenx=1;
        great=10000000;
        memset(best,0,sizeof(best));
        lenbest=0;
        for(i=3;i<=n;i++)
        {
          tmp=sqrt(i);
          for(j=2;j<=tmp;j++)
            if(i%j==0) break;
          if(j>tmp)
          {
            x[lenx]=i;
            lenx++;
          }
        }
        tmp=0; lenmax=0;
        for(i=0;i<lenx;i++)
        {
          tmp+=x[i];
          lenmax++;
          if(tmp>n) { lenmax--; break; }
          if(tmp==n) break;
        }
        dfs(0,n,0);
        for(i=0;i<lenbest;i++) printf("%4d ",best[i]);
        if(!lenbest) printf("No answer");
        printf("\n");
    }
    return 0;
}
    
    

[[it] 本帖最后由 卧龙孔明 于 2008-4-12 17:45 编辑 [/it]]

这个程序对于1998的解:
  3    5    7   11   13   17   19   23   29   31   37   41   43   47   53   59
61   67   71   73   79   83   89   97  101  103  107  109  113  127  131  149
原帖链接:https://bbs.bccn.net/thread-208474-1-1.html

[[it] 本帖最后由 卧龙孔明 于 2008-4-12 16:55 编辑 [/it]]

恩  看看 谢谢孔明 分享了学习ING...........

恩顺便问下  我分析的是 : 既然是从最小的质数 我就从2的质数开始循环相加  到了N<=你输入的数字的时候 就会跳出 在用比如 1998-N 的的结果 然后用 1998-N 这个数判断是不是质数 不是 就拿和从2开始的指数相加 当是质数的时候 比如 1998-N+2 是个质数 替换掉质数2 输出  怎么控制那个N (N是循环相加的和)

ls的算法不能保证有解的一定出解,也就是可能对于一些数据死循环出不来

我的算法主要就是搜索,枚举每一种情况肯定超时严重,因此加了几条很管用的减枝

对n=1998来说的，它可以分解成以下数据。这是标准答案
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107  109 113 131 137 139

针对2008我写了个程序 你看下  是我昨天晚上写的
#include<stdio.h>
#define N 33
int spt(int m)
{
     int i=2;
      while(m%i!=0)
          i++;
          if(m==i)
              return 1;
        else
           return 0;
}      
     
void main()
{  int n,m,c=0,i,j; static a[N];
    printf("请输入2008");
    scanf("%d",&n);
   
     j=0;
     for(i=2;i<=131;i++)    \\这里如果能知道循环的次数的化 就能适合别的数了 我的问题就是这里
     {     
          if (spt(i)>0)
          {        
                  a[j]=i;
                    n=n-i;
               j++;
          }
      }   
         for(j=0;j<N;j++)
         {
           if (spt(n+a[j])>0)
           {
              a[j]=n+a[j];
                 break;
           }      
              
         }
      for(j=0;j<N;j++)
      {
          printf("%d\t",a[j]);
      
      }
}

https://bbs.bccn.net/thread-208533-1-1.html
雨中费燕的求解结果是正确。就是看不懂其算法。

事物的正确答案不只是一个,您可以验证一下我的答案,同样是正确的