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

合数分解成质数之和

热度:335   发布时间:2008-04-11 19:52:21.0
合数分解成质数之和
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;
}
----------------解决方案--------------------------------------------------------
  相关解决方案