将一个正整数n拆分成一些数，即 $a_1+a_2+a_3+...+a_k=n$

求所有的乘积值个数 (即所有不重复的 $a_1*a_2*a_3*...a_k$)

我想到的是一个 $O(n^2/ln(n))$ 的dp,是否有更好的做法

代码贴下

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e4+7,mod=1e9+7;
ll f[N];
bool vis[N];
int a[N];
int tot=0;
int main(){	
	int n; cin>>n;
	a[++tot]=1;
	for(int i=2;i<=n;i++){
		if(vis[i]==0) a[++tot]=i; 
		for(int j=2*i;j<=n;j+=i) vis[j]=1;
	}
	f[0]=1;
	for(int i=1;i<=tot;i++){
		for(int j=0;j<=n;j++){
			if(j-a[i]>=0){
				f[j]+=f[j-a[i]];
				f[j]%=mod;
			}
		}
	}
	cout<<f[n]%mod;
	return 0;
}