如何转换成背包问题呢，我们可以把每个质数当成一个重量

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

#define int long long
int record[1005];
void fun() {
	//record[2] = 1;
	for (int i = 2; i <= 1000; i++) {
		if (!record[i]) {
			for (int j = i * 2; j <= 1000; j += i) record[j] = 1;
		}
	}
}

int n;
int dp[1005];

signed main() {
	fun();
	cin >> n;
	dp[0] = 1;
	for (int i = 2; i <= n; i++) {  // 物品的重量
		if (record[i])  continue;
		for (int j = i; j <= n; j++) {
			dp[j] += dp[j - i];
		}
	}
	cout << dp[n];
}

再看一题，这种有容量限制的都可以转换为背包问题

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

const int N = 1005;
int va[N];
int is[N];
int n;
void fun() {
	va[2] = 1;
	for (int i = 3; i <= n; i++) {
		va[i] += 1;
		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				va[i] += j;
				//if (i / j != j) {
				//	va[i] += i / j;
				//}
			}
		}
	}
	//for (int i = 2; i <= 10; i++) {
	//	cout << i << " " << va[i] << endl;
	//}
}
int dp[N];

int main() {
	cin >> n;
	fun();
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			dp[j] = max(dp[j], dp[j - i] + va[i]);
		}
	}
	cout << dp[n];
}