思路：实际上求的是和小于等于n的质数的种类数！！！
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
int prime[],cnt;
ll dp[][];
bool f[];
void init()
{
cnt=;
for(int i=;i<=;i++){
if(!f[i]) prime[cnt++]=i;
for(int j=;j<cnt&&i*prime[j]<=;j++){
f[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
}
ll dfs(int n,int m)
{
if(dp[n][m]!=-) return dp[n][m];
if(prime[m]>n) return dp[n][m]=;
ll ans=;
int k=;
while(k<=n){
ans+=dfs(n-k,m+);
if(!k) k=prime[m];
else k*=prime[m];
}
return dp[n][m]=ans;
}
int main(){
init();
memset(dp,-,sizeof(dp));
int n;
while(scanf("%d",&n)!=EOF){
printf("%I64d\n",dfs(n,));
}
return ;
}