背包问题 洛谷 [AHOI2001]质数和分解

Question

题目要求： 任何大于 1 的自然数 N，都可以写成若干个大于等于2且小于等于 N 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如9 的质数和表达式就有四种本质不同的形式：9 = 2+5+2 = 2+3+2+2 = 3+3+3 = 2+7 。 这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。 试编程求解自然数 N 可以写成多少种本质不同的质数和表达式。 输入格式 读入一个自然数 N , 2≤N≤1070。 输出格式 依次输出每一个自然数 N 的本质不同的质数和表达式的数目

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
int n,pr[20000],f[20000],a,flag;
void prime(int nn){
    for (int i=2;i<=2075;i++){
        flag=0;
        for (int j=2;j<=sqrt(i);j++){
            if(i%j==0)
                flag=1;
        }
        if(flag==0){
            a+=1;
            pr[a]=i;
        }
    }
}
int main()
{
    cin>>n;
    prime(n);
    f[0]=1;
    for(int i=1;i<=a;++i){
        //cout<<pr[i]<<endl;
        for(int j=pr[i];j<=n;++j)
        f[j]+=f[j-pr[i]];
    } 
    cout<<f[n]<<endl;
    
       return 0; 
}

代码有些问题哪位好人能帮忙解答一下

Answer 1

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
long long t,m,w,dp2[100005],tm1[100001]={0},o;
int truncsqrt(int p){//筛法求素数
    int i;
    for(i=2;i<=p;i++) 
    for(int j=2;j<=p/i;j++) tm1[i*j]=1;
}
int main(){
    int p;
    truncsqrt(201);//打一个质数表，质数为0，非质数为1
    tm1[1]=1;//1不是质数
    while(cin>>p){//循环数
        memset(dp2,0,sizeof(dp2));//记得清零
        dp2[0]=1;
            for(int i=2;i<=p;i++){
                if(tm1[i]==1) continue;
                for(int j=i;j<=p;j++){
                    dp2[j]=dp2[j-i]+dp2[j];
                }
            }
        cout<<dp2[p]<<endl;//直接输出即可
    }
    
}