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

时间:2010-05-07 18:36:55  来源:第二电脑网  作者:第二电脑网

  第二电脑网导读:d; BORDER-LEFT: #cccccc 1px dotted; BORDER-BOTTOM: #cccccc 1px dotted" cellSpacing=0 cellPadding=6 width="95%" align=center border=0>#include<stdio.h>#include<string.h>#include<math.h>#define SIZE 5000#define SIZELINE 20000int x[SIZE]={2},l; /*质数表*/struc...
  正文:

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)
{

合数分解成质数之和问题探究》由第二电脑网原创提供,转载请注明:http://www.002pc.com/master/College/Language/VC/2010-05-07/13915.html


关键字:

关于《合数分解成质数之和问题探究》文章的评论

站内搜索: 高级搜索

热门搜索: Windows style 系统 tr IP QQ CPU 安装 function 注册 if td