当前位置: 代码迷 >> C语言 >> 合数分解成质数之和问题探究
  详细解决方案

合数分解成质数之和问题探究

热度:343   发布时间:2008-04-12 22:13:29.0
合数分解成质数之和问题探究
1.将一个合数分解成多个质数,使分解的各个质数均不等、它们的和等于该合数,且它们中最大的质数最小
算法:DP,背包问题,复杂度约为O( (N/10)^2 )
程序代码:

#include<stdio.h>
#include<string.h>
#include<math.h>
#define SIZE 5000
#define SIZELINE 20000
int x[SIZE]={2},l; /*质数表*/
struct
{
      char ok;
      int l[200];
      short p;
} countline[SIZELINE];
void qsort(int low,int high,int key[])
{
     int i,j,tag;
     i=low; j=high;
     if(i<j)
     {
       tag=key[i];
       do
       {
         while(tag<key[j] && i<j) j--;
         if(i<j)
         {
                key[i]=key[j];
                i++;
                while(tag>=key[i] && i<j) i++;
                if(i<j)
                {
                       key[j]=key[i];
                       j--;
                }
         }
       }while(i<j);
       key[i]=tag;
       qsort(low,j-1,key);
       qsort(i+1,high,key);
     }
}
int main(void)
{
    int i,j,k,tmp;
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        l=1;
        memset(countline,0,sizeof(countline));
        for(i=3;i<=n;i++)
        {
          tmp=sqrt(i);
          for(j=2;j<=tmp;j++)
            if(i%j==0) break;
          if(j>tmp)
          {
            x[l]=i;
            l++;
          }
        }
        countline[0].ok=1;
        for(i=0;i<l;i++)
        {
          for(j=n;j>0;j--)
          {
            if(j<x[i]) break;
            if(!countline[j].ok && countline[j-x[i]].ok)
            {
              countline[j].ok=1;
              countline[j].l[countline[j].p]=x[i];
              countline[j].p++;
              k=0;
              while(k<countline[j-x[i]].p)
              {
                countline[j].l[countline[j].p]=countline[j-x[i]].l[k];
                countline[j].p++; k++;
              }
            }
          }
          if(countline[n].ok) break;
        }
        
        qsort(0,countline[n].p-1,countline[n].l);
        for(i=0;i<countline[n].p;i++) printf("%4d ",countline[n].l[i]);
        printf("\n");
    }
    return 0;
}
   
   
2.将一个合数分解成多个质数,使分解的各个质数均不等、它们的和等于该合数,分解的质数个数最多
算法:搜索+减枝
程序代码:

#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;
}

3.将一个合数分解成多个质数,使分解的各个质数均不等、它们的和等于该合数,使之解为元素个数最多且在元素最多的前提下使最大元素最小
算法:搜索+减枝

程序代码:

#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;
}
搜索更多相关的解决方案: 合数  质数  之和  分解  探究  

----------------解决方案--------------------------------------------------------
顶了  慢慢看
----------------解决方案--------------------------------------------------------
最大的质数最小  ?  这是什么意思```

还有质数是不是就是素数?
----------------解决方案--------------------------------------------------------
例如
10=2+3+5
10=3+7
在这里,10可以表示成以上不同的质数的和,但是,其中5<7,即10=2+3+5中的5是分解的这组数中的最大数,又为所有各组数据中的最大数中最小的数
不知道您是否看明白了
质数就是素数
----------------解决方案--------------------------------------------------------
YES``我明白了```

谢谢``
----------------解决方案--------------------------------------------------------
还有一个问题```什么是合数啊``

多个素数的和算是合数吗?
----------------解决方案--------------------------------------------------------
好象这里大部分人都对算法不感兴趣

算法才是程序的本质和灵魂啊
----------------解决方案--------------------------------------------------------
[bo]以下是引用 [un]死了都要C[/un] 在 2008-4-13 18:53 的发言:[/bo]

还有一个问题```什么是合数啊``

多个素数的和算是合数吗?

大于等于4的整数并且不是质数,那么它就是合数
----------------解决方案--------------------------------------------------------
觉得只有对语法到一定程度才会去看算法.要不也看不懂得....呵呵
----------------解决方案--------------------------------------------------------
[bo]以下是引用 [un]sunkaidong[/un] 在 2008-4-13 18:56 的发言:[/bo]

觉得只有对语法到一定程度才会去看算法.要不也看不懂得....呵呵

算法与语法没有直接关系,算法是一种思想,不仅在信息技术中,在数学等领域同样需要良好的算法,与其选择学习更多华丽的语句,毋宁选择更多的华丽的算法
华丽的语句对程序至多是点缀或减少一点代码长度,而华丽的算法可以使程序效率提高许许多多倍,可以使程序更加的完美
----------------解决方案--------------------------------------------------------
  相关解决方案