50pts求调
查看原帖
50pts求调
1354230
TaojunWang楼主2025/8/1 15:44

感觉思路可能有点问题,但是加上判断j-pr[i]是否是质数的代码后只有20分了

#include<bits/stdc++.h>
using namespace std;
int n,dp[1010],pr[1000],cnt;
//假设每一个质数是n,因为2是最小的质数,所以可以把n拆解为2+(n-2)
//所以只用知道(n-2)的方案数即可 
bool is_prime(int n){
	for(int i=2;i*i<=n;i++){
		if(n%i==0) return false;
	}
	return true;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		if(is_prime(i)) pr[++cnt] = i;
	}
	dp[0] = 1;
	for(int i=1;i<=cnt;i++){
		for(int j=2;j<=n;j++){
			if(j-pr[i]>=0) dp[j] += dp[j-pr[i]];
		}
	}
	cout<<dp[n];
	return 0;
}
2025/8/1 15:44
加载中...