合数分解成质数之和
N是一个合数,求出其最多由多少个[un]最小[/un]不同质数和组成,并要求按小到大输出这些质数。我自己弄了个程序,但是存在些问题(程序中说明处),各位看看怎么改才好。
如果有更好的程序,那就更好了。
对N=2008:
#include "stdio.h"
int ISzhishu(int num){
int i;
if(num==2)
return 1;
if(num==1)
return 0;
for(i=2;i<=num-1;i++)
{
if(num%i==0)
return 0;
}
return 1;
}
main()
{
int i;
int sum=0;
int temp;
int flag=1;
int a[200];
for(i=1;i<200;i++)
a[i]=-1;
i=1;
while(sum<2008)
{
if(ISzhishu(i)==1)
{
sum+=i;
a[i]=1;
}
i++;
}
sum-=2008;
temp=sum;
while(flag==1)
{
while(ISzhishu(temp)==0)
{
temp--;
}
a[temp]=-1;
if(sum>temp )
//此处即存在问题,即可能最后会使sum =1;temp =0,成了死循环
{
temp=sum-temp;
sum=temp;
}
else if(sum==temp )
{
flag=0;
}
}
sum = 0;
for(i=1;i<200;i++)
{
if(a[i]==1)
{
sum += i;
printf("%d ",i);
}
}printf(" sum=%d", sum);
}
----------------解决方案--------------------------------------------------------
是将2008分解质因数吗?
----------------解决方案--------------------------------------------------------
如果是奇数,减去一个3,然后就是n个2
如果是偶数,直接n个2
没意思的题目
----------------解决方案--------------------------------------------------------
飞燕,你不是在搞竞赛吗?怎么有时间过来?呵呵
[[it] 本帖最后由 sunkaidong 于 2008-4-11 21:17 编辑 [/it]]
----------------解决方案--------------------------------------------------------
回复 3# 的帖子
你没看清题目要求,是最小不同的质数 。仔细考虑考虑。 ----------------解决方案--------------------------------------------------------
哦。。。。。看错题目了
----------------解决方案--------------------------------------------------------
[bo]以下是引用 [un]sunkaidong[/un] 在 2008-4-11 20:54 的发言:[/bo]
飞燕,你不是在搞测试吗?怎么有时间过来?呵呵
飞燕,你不是在搞测试吗?怎么有时间过来?呵呵
测试是自动的,我当然有空
----------------解决方案--------------------------------------------------------
#include<stdio.h>
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;
printf("请输入一个数");
scanf("%d",&n);
for(i=2;i<=131;i++)
{
if (spt(i)>0)
{
printf("%d\t",i);
n=n-i;
}
}
printf("%d",n);
} 我做了个分析 '最小'不好定义 你看下 还有
#include<stdio.h>
int spt(int m)
{
int i=2;
while(m%i!=0)
i++;
if(m==i)
return 1;
else
return 0;
}
void main()
{ int n,b,m;
printf("请输入一个数");
scanf("%d",&n);
if(n>=4&&n%2==0)
{
b=n/2;
for(m=2;m<=b;m++)
{
if (spt(m)>0)
if(spt(n-m)>0)
printf("%d\t%d\t\n",m,n-m);
}
}
else
printf("你输入的是错的");
} \\着是我以前写的大于6的偶数是由2个质数组成,希望对你有帮助
----------------解决方案--------------------------------------------------------
我是对你的2008 分析的 恩我本来写 的是 while 判断的 要是最小那不就是从2开始加的么 我是这样理解的
#include<stdio.h>
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;
printf("请输入一个数");
scanf("%d",&n);
for(i=2;;i++)
{
if (spt(i)>0)
{
printf("%d\t",i);
n=n-i;
if(n<=0)
break;
}
}
}
----------------解决方案--------------------------------------------------------
#include "stdio.h"
#include"stdlib.h"
int rem=3;
int a[1000];
int j=0;
int b;
int pn()
{ int flag;
do
{ flag=0;
for(int i=2;i<=rem-1;i++)
if(rem%i==0)
flag=1;
}while(rem++&&flag);
return rem-1;
}
int reduce(int s)
{ int n=pn();
if(s==0)
return 1;
if(s<0)
return 0;
if(s>b)
{
printf("没有结果!");
exit(0);
}
if(reduce(s-n))
{
printf("%d\t",a[j++]=n);
return 1;
}
return(reduce(s+n));
}
int main()
{
scanf("%d",&b);
reduce(b);
return 0;
}
----------------解决方案--------------------------------------------------------