质数和分解

#include<iostream>
#include<string.h>
using namespace std;
const int N=210;

int m;
int f[N][N];
int primes[N];
int cnt=1;
bool st[N];

void init()
{
    for(int i=2;i<=200;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=1;primes[j]*i<=200;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main()
{
    init();//线性筛质数，把每一个质数看成一个物品
    
    while(cin>>m)//背包的最大体积
    {
        
        memset(f,0,sizeof f);//多组数据，每次需要初始化
        
        f[0][0]=1;//一个物品都不选时，体积为0，这个状态时存在的
        
        int n=0;//得到物品个数
        
        for(int i=1;i<cnt;i++)
        if(primes[i]>=m)
        {
            if(primes[i]>m) n=i-1;
            else n=i;
            break;
        }
        
        if(!n) n=cnt-1;
        
        for(int i=1;i<=n;i++)//物品个数 
        for(int j=0;j<=m;j++)//体积 
        {
            f[i][j]+=f[i-1][j];
            if(j-primes[i]>=0)
            f[i][j]+=f[i][j-primes[i]];
        }
        
        printf("%d\n",f[n][m]);
    }
    
    return 0;
}