学步园

58、整数的素数和分解问题
歌德巴赫猜想说任何一个不小于 6 的偶数都可以分解为两个奇素数之和。
对此问题扩展，如果一个整数能够表示成两个或多个素数之和，则得到一个素数和分解式。
对于一个给定的整数，输出所有这种素数和分解式。
注意，对于同构的分解只输出一次（比如 5 只有一个分解 2 + 3，而 3 + 2 是 2 + 3 的同构
分解式）。
例如，对于整数 8，可以作为如下三种分解：
(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3

(3) 8 = 3 + 5

/*
58、整数的素数和分解问题
歌德巴赫猜想说任何一个不小于 6 的偶数都可以分解为两个奇素数之和。
对此问题扩展，如果一个整数能够表示成两个或多个素数之和，则得到一个素数和分解式。
对于一个给定的整数，输出所有这种素数和分解式。
注意，对于同构的分解只输出一次（比如 5 只有一个分解 2 + 3，而 3 + 2 是 2 + 3 的同构
分解式）。
例如，对于整数 8，可以作为如下三种分解：
(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3
(3) 8 = 3 + 5

参考别人的 似懂未懂 
*/
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define M 100000
#define N 100
int vis[M],prime[N];
int k,c;
int dp[N][N],ans[M];  
//dp[i][j] i是质数 j是位置 
void getPrime()
{
	int i,j;
	memset(vis,0,sizeof(vis));
	k=0;
	for(i=2;i<M;i++)
	{
		if(!vis[i])
		{
			prime[k++]=i;
			for(j=2*i;j<M;j+=i)
				vis[j]=1;	
		}
		if(k>=100)
			break;
	}
}

void printAll(int n,int l,int k)//k表示的是小于n的最大质数的位置 
{  
    int i;  
    if(!n)//0输出 
	{  
        for(i=l-1;i>0;i--)  
            printf("%d+",ans[i]); 
		printf("%d",ans[0]); 
        printf("\n");  
        c++;  
        return;  
    }  
    for(i=0;i<=k;i++)
	{  
        if(dp[n][i])
		{  
            ans[l]=prime[i];  
            printAll(n-prime[i],l+1,i);  
        }  
    }  
}  
 
int main()					
{							 
	int n,i,j,z;
	getPrime();
	while(1)
	{
		printf("请输入正整数n（0结束）\n");
		scanf("%d",&n);
		if(n==0) break;
		
		c=0;  
        memset(dp,0,sizeof(dp));  
        for(i=0;prime[i]<=n;i++)  
            dp[prime[i]][i]=1;  //表示dp[i][J] i是质数 j是质数的位置 
   
        for(i=2;i<=n;i++)//所有数 
		{  
            for(j=0;prime[j]<i;j++)//质数的位置j 
			{  
                for(z=j;z>=0;z--) //小于n的所以数的 质数组合 
                    dp[i][j]|=dp[i-prime[j]][z];//z是质数的位置    
            }  
        }  
        printAll(n,0,j-1);  
        printf("%d总共：%d种分法！\n",n, c);  
    }  
	return 0;
}