【HDU - 4345 】Permutation（DP）

#include <cstdio>
#define N 1001
typedef long long ll;
ll dp[N];
bool com[N];
int cnt;
int prime[N];
int main(){
	for(int i=2;i<N;++i)
	if(!com[i]){
		prime[++cnt]=i;
		for(int j=i+i;j<N;j+=i)
			com[j]=true;
	}
	dp[0]=1;
	for(int i=1;i<=cnt;++i)
		for(int j=N-1;j>=prime[i];--j)
			for(int k=prime[i];k<=j&&k<N;k*=prime[i])
				dp[j]+=dp[j-k];
	for(int i=1;i<N;++i)
		dp[i]+=dp[i-1];
	int n;
	while(~scanf("%d",&n))
		printf("%lld\n", dp[n]);
	return 0;
}