题目描述

给定一个正整数n，求将其分解成若干个素数之和的方案总数

输入格式

一行：一个正整数n(n≤1000)

输出格式

一行：一个整数表示方案总数

输入样例

7

输出样例

3

三种情况分别为：

7=7 7=2+5

7=2+2+3

解法

思想

本题可采用完全背包：

  1. 本题给出了n即背包容量，所有素数即为体积为其本身数值的物品。
  2. 由样例7=2+2+3可知，每个物品可以取无限次

代码

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    int t=0,n=0;
    int w[1001]={};
    //这里采用longlong尤其要注意，dp计算方案数，这个方案是可能远大于t，甚至超过int范围
    long long f[1001]={};
    for(int i=2;i<=1000;i++){
            bool zhi=true;
            for(int j=2;j<i;j++){
                    if(i%j==0){
                               zhi=false;
                               }
                    }
            if(zhi){
                    w[++n]=i;
                    }
            }
    cin>>t;
    for(int i=1;i<=n;i++){
            for(int j=1;j<=t;j++){
                    if(j==w[i])
                        f[j]++;
                    else if(j>w[i])
                        f[j]+=f[j-w[i]];
                    }     
            }
    cout<<f[t];
    return 0;
    }