合数分解成质数之和问题探究
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]
觉得只有对语法到一定程度才会去看算法.要不也看不懂得....呵呵
觉得只有对语法到一定程度才会去看算法.要不也看不懂得....呵呵
算法与语法没有直接关系,算法是一种思想,不仅在信息技术中,在数学等领域同样需要良好的算法,与其选择学习更多华丽的语句,毋宁选择更多的华丽的算法
华丽的语句对程序至多是点缀或减少一点代码长度,而华丽的算法可以使程序效率提高许许多多倍,可以使程序更加的完美
----------------解决方案--------------------------------------------------------