#include using namespace std; typedef long long ll; int n,tot; ll p[200],f[2000],ans; int main(){ scanf("%d",&n); for (int i=2;i<=1000;i++) { bool g=true; for(int j=2;j<=trunc(sqrt(i));++j) { if (i%j==0) { g=false; break; } } if (g) tot++,p[tot]=i; } f[0]=1; for(int i=1;i<=tot;++i) for(int j=n;j>=p[i];--j) for(int k=p[i];k<=j;k*=p[i]) f[j]+=f[j-k]; for (int i=0;i<=n;++i) ans+=f[i]; printf("%lld\n",ans); return 0; } //欧拉筛 v[1]=1; tot=0; for (int i=2;x<=n;i++){ if (!v[i]) prime[++tot]=i; for (int j=1;j<=tot&&prime[j]*i<=n;j++){ v[i*prime[j]]=1; if (i%prime[j]==0) break; } }
背包加数论 SCOI2009