蓝桥杯2300 质数拆分

问题描述

将 2022 拆分成不同的质数的和，请问最多拆分成几个？

01背包问题

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;int prime[2025];
int dp[2025];  //dp[j]：和为 j 时的最多拆分质数个数//2022数较小，使用普通的质数判断函数 
bool is_prime(int x)
{if(x<2) return 0;if(x==2) return 1;for(int i=2; i<=sqrt(x); ++i){if(x%i==0) return 0;}return 1;
}int main()
{	int cnt=0;for(int i=2; i<=2022; ++i){if(is_prime(i)){cnt++;prime[cnt] = i;}}for(int i=1; i<=cnt; ++i){//倒序，避免重复使用同一个质数for(int j=2022; j>=prime[i]; j--){dp[j] = max(dp[j], dp[j-prime[i]] + 1);}}cout<<dp[2022];return 0;
}