我们先打个表，列出1~200内所有的素数，然后进行完全背包处理即可(洛谷青藤通用)
#include<bits/stdc++.h>
#define int long long
const int P_count=46;
using namespace std;
int n,dp[211],sum;
int prime[211]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199};//究极打表
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//输入加速
while(cin>>n){
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=P_count;i++){
for(int j=prime[i];j<=200;j++){
dp[j]+=dp[j-prime[i]];
}
}
cout<<dp[n]<<"\n";
}
return 0;
}
下面附上打表代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,dp[211];
int prime[211];
bool is_prime(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0) return false;
}
return true;
}
void get_prime(){
prime[++top]=2;
for(int i=3;i<=200;i+=2){
if(is_prime(i)){
prime[++top]=i;
}
}
return ;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
get_prime();
for(int i=1;i<=top;i++){
cout<<prime[i]<<" ";
}实验
return 0;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~完美的结束~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~