虽然我的程序是正确的，但我并没有找到有效的剪枝算法。 xyhx, Liyanguestc能否将程序改改，提交一个正确的程序，让大家学习学习。
  楼主，如果你不忙的话，能否也写一个标准程序，让大家学习学习。

#include<iostream>
using namespace std;

int prime[20][6],n;
__int64 max;

//获得需要的素数及素数得幂，这一段写得太丑陋了，大家包含
//分解成太大的数，显然不是最优解。n<=300，这些已经足够用了。
void getPrime()    
{
    int i,j;
    for (i=0;i<20;i++)
        for (j=0;j<6;j++)
            prime[i][j]=1011;
    prime[0][0]=2;prime[0][1]=4;prime[0][2]=8;prime[0][3]=16;prime[0][4]=32;
    prime[1][0]=3;prime[1][1]=9;prime[1][2]=27;
    prime[2][0]=5;prime[2][1]=25;
    prime[3][0]=7;
    prime[4][0]=11;
    prime[5][0]=13;
    prime[6][0]=17;
    prime[7][0]=19;
    prime[8][0]=23;
    prime[9][0]=29;
    prime[10][0]=31;
    prime[11][0]=37;
    prime[12][0]=41;
    prime[13][0]=43;
    prime[14][0]=47;
    prime[15][0]=53;
    prime[16][0]=59;
}

void Try(int last,int p,__int64 m)//搜索。仅在getprime()获得的数中间搜索，规模不大
{
    if (p<16) 
    {
        int i=0;
        while (prime[p][i]<=last)
        {
            Try(last-prime[p][i],p+1,m*prime[p][i]);
            i++;
        }
        Try(last,p+1,m);
    }
    if (last!=1 && m>max) max=m;
}

void MonkeyDance(const int n, int* maxStep)
{
    getPrime();
    max=n;
    Try(n,0,1);
    if (n>6) Try(n-6,2,6);
    *maxStep=int(max%10000);
}


这个作为参考，程序并不复杂，简单的搜索剪枝，但是考虑算法的时候要很小心。

如果程序有错请回帖告知。

看了这次的分析，我知道我的思路是正确的。
用程序写出来就是得不到正确答案，所以不敢上交（不希望太现世了），汗啊！！！
但我还是很希望大家能帮我找找错在哪里了，请不吝赐教！！！

int main()
{
    void MonkeyDance(int n,int *maxstep);       /*求最多的步数，存在指针maxstep里*/
    void Array(int a[],int i,int n,int *maxstep);     /*求互质数序列，并存于数组a中*/
    int Multiple(int a[]);         /*求数组乘积*/
    int Compare(int a,int b);    /*比较两数是否互质*/
    int maxstep,monkeynum;
    int *maxst;
    maxst=&maxstep;
    monkeynum=200;
    MonkeyDance(monkeynum,maxst);
    printf("%d\n",maxstep);
    getch();
    return 0;
}
void MonkeyDance(int n,int *maxstep)
{
    int i,j,contain[200];   /*存互质数序列*/
    if(n<=1)
    {
        printf("error!\n");
        return;
    }
    *maxstep=n;
    if(n==2 || n==3 || n==4) return;
    for(i=0;i<200;i++) contain[i]=0;
    for(i=0,j=2;j<n/2;j++)
    {
        contain[i]=j;
        Array(contain,i,n-j,maxstep);
    }
    return;
}

void Array(int a[],int i,int n,int *maxstep)
{
    int max,j,i1,k;
    if(n==0)
    {
        max=Multiple(a);
        if(max>*maxstep)
        {
            *maxstep=max;
        }
        return;
    }
    else if(n<a[i]) return;
    else
    {
        for(j=a[i]+1;j<=n;j++)
        {
            for(i1=0;i1<=i;i1++)
            {
                if(Compare(a[i1],j)==1) continue;
                else break;
            }
            if(i1==i)
            {
                for(k=i+1;k<200;k++) a[k]=0;
                a[i+1]=j;
                Array(a,i+1,n-j,maxstep);   /*递归调用*/
            }
        }
        return;
    }
}

int Multiple(int a[])
{
    int mul=1,i;
    for(i=0;;i++)
    {
        if(a[i]!=0) mul=mul*a[i];
        else break;
    }
    return mul;
}

int Compare(int a,int b)
{
    int i,commax;
    commax=a>b?b/2:a/2;
    for(i=2;i<=commax;i++)
    {
        if(a%i==0 && b%i==0) return 0;
        else continue;
    }
    if(a%b==0 || b%a==0) return 0;
    return 1;
}


下次努力了！！！

下次该我出题了，请楼主告诉我，如何出题，使得回复是隐藏的，如何结贴。

[quote]下次该我出题了，请楼主告诉我，如何出题，使得回复是隐藏的，如何结贴。[/quote]
发帖的时候要在分类里选择“编程比赛”。帖子发表以后，点修改，就会多一个“结贴后才能查看回帖”的选项。在修改旁边有结贴等选项。

[quote][quote]回1楼，分解后的若干个数，当最小公倍数最大，它们不一定互质。比如21，最好的分解是2+3+4+5+7，而不是互质的情况。[/quote]

所以只能尽量。因为最后计算乘积的话，合数因子会对其他的质数因子产生影响，例如2、3、4、5、7中因为2是4的因子，因此2不能算，只能算4。

我的想法是，当对一个数N进行分解的时候，选择一个接近N/2而且与其他数不重复的质数，记为Z(2/N)，另外一个数当然就是R&nbsp;=&nbsp;N&nbsp;-&nbsp;Z(2/N)，Z(2/N)当然不会是其他数的因子，反之亦然，因此接下来测试R：

如果R是质数，且唯一，那么这种分解就成功了，如果不唯一，则失败；

如果存在一个其它的质数数Zt，使得Zt是R的因子，那么去掉Zt后分解成功；

如果存在一个其它的合数Ot，使得Ot是R的因子或者R是Ot的因子，就看N是否为质数，如果是，就不分解。如果不是，就保留R和Ot的大者，去掉因子。如果不存在其他的数与R有以上关系，则继续下一轮分解。还有一点就是如果Z*R<=N，则必须继续选取其他的Z和R。并且R不能为1。

例如对于21，
第一轮：
Z(2/N)=11，R=10，分解成功
（11、10）

第二轮：
对于11分解为Z=5，R=6，成功；
对于10分解为Z=5，R=5，质数5重复，因此继续选择Z和R。Z=3，R=7，成功
（5，6，3，7）

第三轮：
对于5分解为Z=2，R=3，由于质数3重复，所以5不能分解
对于6分解为Z=3，R=3，由于质数3重复，所以继续选择Z和R。Z=2，R=4，考虑到2是4的因子，因此去掉2，保留4。
对于3无法分解。
对于7分解为Z=3，R=4，4重复，而N=7为质数，因此不能分解
（5，[2]，4，3，7）

第四轮分解
对于5，不能分解
对于2、3、7也不能分解
对于4，分解为Z=2、R=2，质数2重复，不能分解
（5，[2]，4，3，7）为最终结果，其中[2]被去掉，不参与相乘。


[/quote]
跟我的分法是接近呵呵

在9楼提交的没有改为long int 我用的是VC觉得应该没问题，^o^

在22楼提交的实在是对不起，由于时间匆忙，提交后我自己都运行不了，后来发现是有两句语句忘写了。正确的是下面：
#include<malloc.h>
void MonkeyDance(const int no, int* maxStep)
{    
    int i,count,num;
    int *mon,*str;//指向数组
    int *pback,*pforw;//指向数组元素
    long int temp,max=0,mid=1,t;
    long int gcd(long int a,long int b);   
    long int ComNum(int *mark,int count);
    for(i=2,count=0,num=0;num+i<=no;i++,count++)
        num+=i;
    num-=(i-1);
    str=mon=(int * )calloc(count+1,sizeof(int));
    if(mon==NULL)
        printf("Allocat memory failed!\n");
    else
    {
        for(i=0;i<count-1;i++)
            *mon++=i+2;
        *mon=no-num;
        if(count==1)        
            max=str[0];    
        else
        {
            pback=str+count-2;pforw=pback+1;
            do
            {
                temp=(*pback)+(*pforw);
                if( temp>=((*pback)+2)*3)
                {
                    (*pback)++;
                    while(1)
                    {
                        if(temp>=(*pback+1)*3)
                        {
                            temp-=*pback;
                            *pforw=(*pback)+1;
                            pback++;pforw++;
                            count++;
                        }
                        else
                        {
                            *pforw=temp-(*pback);                            
                            break;
                        }
                    }
                }
                   mid=ComNum(str,count-2);
                while(1)
                {
                    if( *pback<*pforw )
                    {
                        t=(*pback)*(*pforw)/gcd(*pback,*pforw);
                        t=mid*t/gcd(mid,t);
                        max=t>max?t:max;
                        [color=FF0000](*pback)++;(*pforw)--;[/color]                    }
                    else
                    {                                
                        *pback+=(*pforw);
                        if(pback!=str)                        
                            pback--;
                        pforw--;                        
                        count--;                    
                        break;
                    }
                }            

            }while(pforw!=str);
        }
    }
    max=str[0]>max?str[0]:max;
    *maxStep=max%10000;    
}
void Print(int *addr,int n)
{
    int i;
    for(i=0;i<n;i++)
        printf("%d ",*addr++);
    putchar('\n');
}
long int gcd(long int a,long int b)
{
    if (a%b==0) return b;
    return gcd(b,a%b);
}
long int ComNum(int *mark,int count)
{
    int i;
    long int res=1;
    for(i=0;i<count;i++)
        res=mark[i]*res/gcd(mark[i],res);
    return res;        
}

恩 程序结果正确。但是速度没有大的提升。