合数分解成质数之和问题探究
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;
}
