一道 01 背包硬控我半小时
#define Code using
#define by namespace
#define stringdp100005 std
#include<bits/stdc++.h>
Code by stringdp100005;
int n,dp[205];
int pr[205],c;
bool vis[205];
void init(){
for(int i=2;i<=200;i++){
if(!vis[i]) pr[++c]=i;
for(int j=1;j<=c&&i*pr[j]<=200;j++){
vis[i*pr[j]]=1;
if(i%pr[j]==0) break;
}
}
}
signed main(){
init();
cin>>n;
for(int i=1;i<=c;i++){
for(int j=n;j>=pr[i];j--){
dp[j]=max(dp[j],dp[j-pr[i]]+1);
}
}
cout<<dp[n];
return 0;
}
