第65次编程比赛 — 编程爱好者社区

主题：第65次编程比赛

雨中飞燕 [专家分：18980] 发布于 2008-04-14 14:06:00

问题题目：整数的质数和分解

[color=0000FF]题目描述：[/color]
把一个任意大于6的整数，分解为质数之和的形式，
要求这些质数均不相等，并且最大的那个质数尽可能地小，
以此为前提的情况下，还要让其分解的质数尽可能地多。
当有多个满足以上条件的方案时，
要求次大的质数也尽可能地小，
然后次三大的质数也尽可能地小，以此类推。

[color=0000FF]输入：[/color]
多组数据，一行一组，
一组仅有一个数n(6 < n <= 1e9)
当n为0时结束程序

[color=0000FF]输出：[/color]
输出分解的方案，详细形式请参看样例数据，
一行输入对应一行输出。
注意行末不要有空格，数与数之间有空格。

[color=0000FF]样例输入：[/color]
7
11
24
42
0

[color=0000FF]样例输出：[/color]
7 = 2 5
11 = 11
24 = 11 13
42 = 2 5 7 11 17

[color=0000FF]其它信息：[/color]
注意，24还有一组解为 2 3 19，
不过最大质数较大，尽管它分解的质数更多；
42还有一组解为 2 3 7 13 17，不过次大质数较大，
所以这种解均不合题意

[color=0000FF]代码提交：[/color]
请把您的完整代码直接回复于本帖子，回复帖子将不可见，
但在结帖以前你仍然可以编辑您的帖子。
如果您希望能够马上测试您的代码，请提交到[url]http://yzfy.org/bbs/viewthread.php?tid=755[/url]
若有问题，请在这帖子里提问[url]http://bbs.pfan.cn/post-272985.html[/url]

最后更新于：2008-04-14 14:08:00

本帖地址： http://bbs.pfan.cn/post/272986.html

回复列表（共10个回复）

沙发

hmilywam [专家分：350] 发布于 2008-04-14 19:25:00

参考一下答案；

板凳

boxertony [专家分：23030] 发布于 2008-04-16 13:01:00

发错了，抱歉

3 楼

linzerong [专家分：0] 发布于 2008-04-16 16:18:00

[em2]

4 楼

ws0415 [专家分：3370] 发布于 2008-04-20 14:25:00

[code=c]
#include <iostream>
#include <cstdlib>
using namespace std;

static int num=0;//质数个数
static bool tag=true;

//转换成一个寻找子集的问题
int *set;//set[10]={23,19,17,13,11,7,5,3,2};
int *a;//a[9]={0};
long n;//输入的质数

int* Down_Prime(int);
void Output(int*);
void initialize(void)//输入的数为n
{
    delete []set;
    delete [] a;
    int *data=Down_Prime(n);
    set=(int*)malloc(sizeof(int)*num);
    a=(int*)malloc(sizeof(int)*num);
    memset(a,0,sizeof(a));

    int *p=data;
    int *q=set;
    while(*p)
        *q++=*p++;//质数复制到set集合中
    Output(data);

    tag=true;
}
int* Down_Prime(int n)//输出不大于n的所有质数
{
    int *array=(int*)malloc(sizeof(int)*n/2);
    int *p=array;
    num=0;

    if(n>2)
    {
        for(int i=n;i>2;i--)
        {
            if(i%2==0)
                continue;//排除偶数
            int j=3;
            while(j<i/2)
            {
                if(i%j==0)
                    goto Label;
                j=j+2;
            }
            *p++=i;
            num++;
Label:
            ;
        }
        *p++=2;
        num++;
    }
    *p=0;//0作为结束标志

    return array;
}
void Output(int *p)
{
    if(*p)
    {
        cout<<*p++<<" ";
        Output(p);
    }
}

int sum(int *a)
{
    if(*a==0)
        return 0;
    else
    {
        int temp=*a++;
        return temp+sum(a);
    }
}
void output(int *a)
{
    int *p=a;
    while(*p&&(p-a)<10)
        cout<<*p++<<" ";
    cout<<endl;
}
void cset(int i)
{
    if(i==num)
    {
        int sum=0;
        for(int k=0;k<num;k++)
            if(a[k])
                sum+=set[k];
        if(sum==n)
        {
            for(k=num-1;k>0;k--)
                if(a[k])
                    cout<<set[k]<<" ";
            cout<<endl;
            tag=false;
        }
    }
    else
        if(tag)
        for(int j=0;j<2;j++)
        {
            a[i]=j;
            cset(i+1);
        }
}

int main()
{
    while(cin>>n)
    {
        initialize();
        cout<<endl<<num<<endl;
        cset(0);
        cout<<endl;
    }
    delete []set;
    delete []a;

    return 0;
}

[/code]

5 楼

ws0415 [专家分：3370] 发布于 2008-04-20 15:02:00

[code=c]
#include <iostream>
#include <cstdlib>
using namespace std;

static int num=0;//质数个数
static bool tag=true;

//转换成一个寻找子集的问题
int *set;//set[10]={23,19,17,13,11,7,5,3,2};
char *a;//a[9]={0};
long n;//输入的质数

int* Down_Prime(int);
void Output(int*);
void initialize(void)//输入的数为n
{
    delete []set;
    delete [] a;
    int *data=Down_Prime(n);
    set=(int*)malloc(sizeof(int)*num);
    a=(char*)malloc(sizeof(char)*num);
    memset(a,0,sizeof(a));

    int *p=data;
    int *q=set;

    while(*p)
        *q++=*p++;
    Output(data);
    cout<<endl;

    tag=true;
}
int* Down_Prime(int n)//输出不大于n的所有质数
{
    int *array=(int*)malloc(sizeof(int)*n/2);
    int *p=array;
    num=0;

    if(n>2)
    {
        for(int i=n;i>2;i--)
        {
            if(i%2==0)
                continue;//排除偶数
            int j=3;
            while(j<i/2)
            {
                if(i%j==0)
                    goto Label;
                j=j+2;
            }
            *p++=i;
            num++;
Label:
            ;
        }
        *p++=2;
        num++;
    }
    *p=0;//0作为结束标志

    return array;
}
void Output(int *p)
{
    if(*p)
    {
        cout<<*p++<<" ";
        Output(p);
    }
}

int sum(int *a)
{
    if(*a==0)
        return 0;
    else
    {
        int temp=*a++;
        return temp+sum(a);
    }
}
void output(int *a)
{
    int *p=a;
    while(*p&&(p-a)<10)
        cout<<*p++<<" ";
    cout<<endl;
}
void cset(int i)
{
    if(i==num)
    {
        int sum=0;
        for(int k=0;k<num;k++)
            if(a[k])
                sum+=set[k];
        if(sum==n)
        {
            for(k=num-1;k>=0;k--)
                if(a[k])
                    cout<<set[k]<<" ";
            cout<<endl;
            tag=false;
        }
    }
    else
        if(tag)
        for(int j=0;j<2;j++)
        {
            a[i]=j;
            cset(i+1);
        }
}

int main()
{
    while(cin>>n)
    {
        initialize();
        cout<<endl<<num<<endl;
        cset(0);
        cout<<endl;
    }
    delete []set;
    delete []a;

    return 0;
}
[/code]

6 楼

zhao1988long [专家分：0] 发布于 2008-04-20 20:56:00

#include<iostream.h>
#include<stdio.h>
#include<math.h>
struct JIEDIAN
{
    long a;
    JIEDIAN *next;
};
int sum;
int max;
long *shu;
JIEDIAN *A;
long *aa;
long *AA;
void input()
{
    long i=0;
    JIEDIAN *temp,*a1=A;
    cout<<"请输入大于6的数:!"<<endl;
    scanf("%d",&i);
    while(i!=0)
     {
        temp=new JIEDIAN;
        temp->a=i;
        temp->next =NULL;
        a1->next=temp;
        a1=temp;
        cout<<"请输入数:!"<<endl;
        do{
            if(i<=6)cout<<"输入有错!"<<endl;
            scanf("%d",&i);
        }while(i<=6&&i!=0);
    }
}
void  Shushu(long aa)
{
   JIEDIAN *B,*b,*temp;
    B=new JIEDIAN; B->a=0; B->next =NULL;
    b=B;           sum=0;  int i,j;
    for(j=2;j<=aa;j++)
    {
      for(i=2;i<=sqrt(j);i++)
          if(j%i==0)break;
        if(j==2||j==3||i>sqrt(j))
        {
          temp=new JIEDIAN;
          temp->a=j;
          temp->next=NULL;
          sum+=1;
          b->next=temp;
          b=temp;
        }
     }
     B=B->next;
     shu=new long[sum+1];
     for(i=1;i<=sum;i++)
     {
        shu[i]=B->a;
        B=B->next;
     }
}
void Separate(long a,int ij,int I,long asum)
{
    int i,j;
    long temp;
    for(i=ij;i<=sum;i++)
    {
       temp=0;
       temp=asum+shu[i];
       for(j=I;j<=sum;j++)aa[j]=0;
      if(temp<a)
      {
          aa[I]=shu[i];
         Separate(a,i+1,I+1,temp);
      }
      if(temp==a)
      {
           aa[I]=shu[i];
           int j=I, n,mm=max;
           if(aa[j]<AA[mm])
            {
                  for(n=0;n<=sum;n++)AA[n]=0;
                  for(n=0;n<=I;n++)AA[n]=aa[n];
                  max=I;
                  return;
            }
            if(aa[j]==AA[mm])
            {
                int MAx=max-1;
                for(n=I-1;n>=1&&MAx>=1;n--,MAx--)
                    if(AA[n]>aa[MAx])
                    {
                       for(n=0;n<=sum;n++)AA[n]=0;
                       for(n=1;n<=sum;n++)AA[n]=aa[n];
                       max=I;
                       return;
                    }
            }
            if(mm==0)
            {
                for(n=1;n<=sum;n++)AA[n]=aa[n];
                max=I;
                return;
            }
            if(aa[j]>AA[mm])return ;
      }
    }
}
void main()
{
    long asum=0;
    JIEDIAN *a;
    A=new JIEDIAN;
    A->a=0;
    A->next =NULL;
    input();
    a=A->next;
    while(a!=NULL)
    {
      Shushu(a->a);
      aa=new long[sum+1];
      max=0;
      AA=new long[sum+1];
      for(int i=0;i<=sum;i++)
          aa[i]=0;
      Separate(a->a,1,1,asum);
      i=1;
      cout<<a->a<<"=";
      while(AA[i]!=0)cout<<AA[i++]<<" ";
      cout<<endl;
      a=a->next;
    }
}

7 楼

zhao1988long [专家分：0] 发布于 2008-04-21 07:37:00

#include<iostream.h>
#include<stdio.h>
#include<math.h>
struct JIEDIAN
{
    long a;
    JIEDIAN *next;
};
int sum;              //用于保存每一个数的质数的个数
int max;
long *shu;            //存放一个数的每一个质数,用数组，方便写程序
JIEDIAN *A;           //存放输入的数
long *aa;             //临时保存一个数的分解的质数的一种情况
long *AA;            //保存符合要求的
void input()         //输入数
{
    long i=0;
    JIEDIAN *temp,*a1=A;
    cout<<"请输入大于6的数:!"<<endl;
    scanf("%d",&i);
    while(i!=0)
     {
        temp=new JIEDIAN;
        temp->a=i;
        temp->next =NULL;
        a1->next=temp;
        a1=temp;
        cout<<"请输入数:!"<<endl;
        do{
            if(i<=6)cout<<"输入有错!"<<endl;
            scanf("%d",&i);
        }while(i<=6&&i!=0);
    }
}
void  Shushu(long aa)     //求每一个数的质数并且保存在long shu[sum]中
{
   JIEDIAN *B,*b,*temp;
    B=new JIEDIAN; B->a=0; B->next =NULL;
    b=B;           sum=0;  int i,j;
    for(j=2;j<=aa;j++)
    {
      for(i=2;i<=sqrt(j);i++)
          if(j%i==0)break;
        if(j==2||j==3||i>sqrt(j))
        {
          temp=new JIEDIAN;
          temp->a=j;
          temp->next=NULL;
          sum+=1;
          b->next=temp;
          b=temp;
        }
     }
     B=B->next;
     shu=new long[sum+1];
     for(i=1;i<=sum;i++)
     {
        shu[i]=B->a;
        B=B->next;
     }
}
void Separate(long a,int ij,int I,long asum)//对于每一个数实现分解
/*
在每一次递归中把符合要求的shu【i】加到上一层的asum中
比较asum和a是否相等
a-----需要分解的数，在递归里面不变
ij----在数组shu【】中，当前递归的可以取的数的下标的最小值
I-----临时aa【】数组中的元素的个数，
asum---上一次递归后的和

*/
{
    int i,j,n;
    long temp;
    for(i=ij;i>=1;i--)
    {
       if(shu[i]*i+asum<a)return;
       temp=0;
       temp=asum+shu[i];
       aa[I]=shu[i];
      for(j=I+1;j<=sum;j++) aa[j]=0;
      if(temp<a)
      {
         Separate(a,i-1,I+1,temp);
      }
      if(temp==a)
      {
         max=I;
         for(n=0;n<=max;n++)AA[n]=0;
         for(n=0;n<=I;n++)AA[n]=aa[n];
         return;
      }
    }
}
void main()
{
    long asum=0;
    int i=0;
    JIEDIAN *a;
    A=new JIEDIAN;
    A->a=0;
    A->next =NULL;
    input();
    a=A->next;
    while(a!=NULL)
    {
      Shushu(a->a);
      aa=new long[sum+1];
      max=0;
      AA=new long[sum+1];
      for(i=0;i<=sum;i++)
          aa[i]=0;
      Separate(a->a,sum,1,asum);
      cout<<a->a<<"=";
      while(max>0)cout<<AA[max--]<<" ";
      cout<<endl;
      a=a->next;
    }
    cin>>asum;
}

8 楼

yfbsg [专家分：30] 发布于 2008-04-21 13:13:00

#include<stdio.h>
#include<math.h>
#define MAXNUM 10000
long int nextprime(long int i)
{long int number,j;
int f;
for(number=i+1;number<=1000000000;number++)
{
f=0;
for(j=2;j<=sqrt(number);j++)
{
if((number%j)==0)
{
f=1;
break;
}//if
}//for
if((f==0)&&(number>1))
return number;
}//for
return -2;
}
void slove(long int num)
{
long int a[MAXNUM],number,i,j;
float b[MAXNUM];
if((num<7)||(num>1000000000))
{
printf("%ld 超界",num);
return;
}
int end=0;
a[end]=0;
b[0]=0;
number=num;
i=0;
j=1;
int close=0;
while((a[end]==0)||(close==0))
{
if(a[end]!=0)
{
j=b[i];
number+=j;
j=b[i];
}
while(number!=0)
{
b[i]=nextprime(j);
if(b[0]>num)
break;
if(number>=b[i])
{
number-=b[i];
j=b[i];
i++;
}//if
else
{
while(i>0)
{
i--;
j=b[i];
number+=j;
b[i]=nextprime(j);
if(number>=b[i])
{
number-=b[i];
j=b[i];
i++;
break;
}//if
}//while
}//else
}//while
i--;
if(a[end]==0)
{
int plj;
for(plj=0;plj<=i;plj++)
{
a[plj]=b[plj];
end=plj;
}//for
}//if
else
{
int sub,change;
for(sub=0;(end>=sub)&&(i>=sub);sub++)
{
if(a[end-sub]>b[i-sub])
{
change=1;
break;
}//if
else if(a[end-sub]<b[i-sub])
{
change=-1;
break;
}
else change=0;
}//for
if(change==1)
{
int plj;
for(plj=0;plj<=i;plj++)
{
a[plj]=b[plj];
end=plj;
}//for
}//if
}//else
long int ss=nextprime(b[0]);
if(ss>num)
close=1;
else
close=0;
}
printf("%ld = ",num);
for(int plj=0;plj<=end;plj++)
{
printf("%ld ",a[plj]);
}
printf("\n");
}
int main(){
    long int que[1000];
    int thenum=0,r;
    scanf("%ld",&que[0]);
    while(que[thenum]!=0)
    {
    thenum++;
    scanf("%ld",&que[thenum]);
    }
    printf("\nanswer:\n");
    for(r=0;r<thenum;r++)
    slove(que[r]);
    getchar();
    getchar();
}

9 楼

yfbsg [专家分：30] 发布于 2008-04-21 13:20:00

//刚才发的好像让我不小心删了个括号。。重发一下
#include<stdio.h>
#include<math.h>
#define MAXNUM 10000
long int nextprime(long int i)
{
long int number,j;
int f;
for(number=i+1;number<=1000000000;number++)
{
f=0;
for(j=2;j<=sqrt(number);j++)
{
if((number%j)==0)
{
f=1;
break;
}//if
}//for
if((f==0)&&(number>1))
return number;
}//for
return -2;
}
void slove(long int num){
long int a[MAXNUM],number,i,j;
float b[MAXNUM];
if((num<7)||(num>1000000000))
{printf("%ld 超界",num);
return;
}
int end=0;
a[end]=0;
b[0]=0;
number=num;
i=0;
j=1;
int close=0;
while((a[end]==0)||(close==0)){
if(a[end]!=0)
{
j=(long int)b[i];
number+=j;
j=(long int)b[i];
}
while(number!=0)
{
b[i]=nextprime(j);
if(b[0]>num)
break;
if(number>=b[i])
{
number-=(long int)b[i];
j=(long int)b[i];
i++;
}//if
else
{
while(i>0)
{
i--;
j=(long int)b[i];
number+=j;
b[i]=nextprime(j);
if(number>=b[i])
  {
  number-=(long int)b[i];
j=(long int)b[i];
i++;
break;
}//if
}//while
}//else
}//while
i--;
if(a[end]==0)
     {
     int plj;
     for(plj=0;plj<=i;plj++)
     {a[plj]=(long int)b[plj];
     end=plj;
     }//for
     }//if
     else
     {
         int sub,change;

         for(sub=0;(end>=sub)&&(i>=sub);sub++)
         {
         if(a[end-sub]>b[i-sub])
         {change=1;
         break;
         }//if
         else if(a[end-sub]<b[i-sub])
         {change=-1;
         break;
         }
         else change=0;
         }//for

         if(change==1)
         {int plj;
          for(plj=0;plj<=i;plj++)
          {a[plj]=(long int)b[plj];
          end=plj;
          }//for
          }//if
     }//else
    long int ss=nextprime((long int)b[0]);
     if(ss>num)
      close=1;
      else
     close=0;
     }
     printf("%ld = ",num);
     for(int plj=0;plj<=end;plj++)
     {printf("%ld ",a[plj]);
     }
     printf("\n");
}

int main(){
    long int que[1000];
    int thenum=0,r;
    scanf("%ld",&que[0]);
    while(que[thenum]!=0)
    {
    thenum++;
    scanf("%ld",&que[thenum]);
    }
    printf("\nanswer:\n");
    for(r=0;r<thenum;r++)
    slove(que[r]);
    getchar();
    getchar();
}

10 楼

zhao1988long [专家分：0] 发布于 2008-04-21 18:29:00

#include<iostream.h>
#include<stdio.h>
#include<math.h>
struct JIEDIAN
{
    long a;
    JIEDIAN *next;
};
int many=0;             //输入的数的个数
int max=0;            //最大数的质数的个数
long *shu;              //存放输入的数
long *zhishu;            //存放输入的最大数的每一个质数,用数组，方便写程序
long *zhishuhe;          //存放前面的质数的和
int *tempOK;           //shu对应的位置的数组暂时是否存在0和1表示
int *OK;                //保存最符合要求的--(同上*tempOK;)
int success=0;           //标记分解成功
void input()          //输入数
{
    long i=0,shumax=0,j; //shumax输入的数的最大值
    max=4;         //一定存在2.3.5.7这四个质数
    JIEDIAN *temp,*a1,*A;
    A=new JIEDIAN;                       //初始化变量
    A->a=0;                              //第一个结点不用
    A->next =NULL;
    a1=A;
    cout<<"请输入大于6的数:!"<<endl;
    scanf("%d",&i);
    shumax=i;
    while(i!=0)
     {
        temp=new JIEDIAN;
        temp->a=i;
        temp->next =NULL;
        a1->next=temp;
        a1=temp;
        cout<<"请输入数:!"<<endl;
        do{
            if(i<=6)cout<<"输入有错!"<<endl;
            scanf("%d",&i);
        }while(i<=6&&i!=0);
       if(i>shumax) shumax=i;
       many+=1;
    }
    a1=A->next;
    shu=new long[many+1];
    for(i=1;i<=many;i++,a1=a1->next)
        shu[i]=a1->a;            //存放输入的数
                 //生成质数并且保存在long shu[sum]中
                 //求每一个数的质数并且保存在long shu[sum]中
    JIEDIAN *B,*b;   //临时变量存放最大数的质数
    B=new JIEDIAN; B->a=0; B->next =NULL;//第一个结点不用
    b=B;
    for(j=9;j<=shumax;j+=2)
    {
      for(i=3;i<=sqrt(j);i+=2)
          if(j%i==0)break;
        if(i>sqrt(j))
        {
          temp=new JIEDIAN;
          temp->a=j;
          temp->next=NULL;
          max+=1;
          b->next=temp;
          b=temp;
        }
     }
     B=B->next;
     zhishu=new long[max+1];          //头结点不用
     OK=new     int[max+1];           //对应的位置的数组shu是否存在0和1表示
     tempOK=new int[max+1];
     zhishuhe=new long[max+1];
     zhishu[1]=2;zhishu[2]=3;zhishu[3]=5;zhishu[4]=7;
     zhishu[0]=zhishuhe[0]=tempOK[0]=0;
     for(i=1;i<=max;i++)
     {
        if(i>4)
        {
            zhishu[i]=B->a;
            B=B->next;
        }
        zhishuhe[i]=zhishuhe[i-1]+zhishu[i];
        tempOK[i]=0;
     }
}
void Separate(long a,int ij,long asum)//对于每一个数实现分解
/*/ 在每一次递归中把符合要求的shu【i】加到上一层的asum中
  比较asum和a是否相等
a-----需要分解的数，在递归里面不变
ij----在数组shu【】中，当前递归的数的最小值
asum---上一次递归后的和*/
{
    if(ij==0)return;
    int i,j;
    long temp;
    for(i=1;i>=0;i--)//shu【i】为当前递归可以取的值的状态-0：不取  1---取
    {
        if(asum+zhishuhe[ij]+i*zhishu[ij]<a)return;
        for(j=0;j<ij;j++)tempOK[j]=0;
        tempOK[ij]=i;
        temp=i*zhishu[ij]+asum;
        if(temp<a)
        {
           Separate(a,ij-1,temp);
        }
        if(temp==a)
        {
            for(j=0;j<=max;j++)OK[j]=tempOK[j];
            success=1;
        }
    }

}
void main()
{
    long asum=0;
    int i=10,ii,j=1;
    input();                            //输入数据
    while(j<=many)                      //对于输入的每一个数据足一考察
    {

       for(i=3;i<=max;i++)
          if(zhishuhe[i]>=shu[j])
          {ii=i;i=max;}
         do
         {
          success=0;
          ii=ii>max?max:ii;
          Separate(shu[j],ii,asum);       ////对于每一个数实现分解
          ii+=1;
      }while(success==0);
      cout<<shu[j]<<"=";
      for(i=1;i<=max;i++)
      {
          if(OK[i]==1)cout<<zhishu[i]<<" ";
      }
      cout<<endl;
      j++;
    }
    cin>>asum;
}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：第65次编程比赛

回复列表（共10个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第65次编程比赛

回复列表 （共10个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共10个回复）