问题标题: 酷町堂：3266 整数的分解

3266   整数的分解

经验值：400 时间限制：1000毫秒

题目描述 Description

哥德巴赫猜想到现在也没有被证明：任何一个大于2的偶数，都可以写成两个素数之和；

三素数定理已被证明：任何一个大于等于7的奇数都能够写成三个素数之和。

你的任务不是去验证上述猜想和定理，而是求出：给定一个正整数，把它分解成若干个素数之和的形式，一共有多少种不同的分解方法。

例如7可以分解成1或2或3个素数之和：7 = 7 = 2 + 5 = 2 + 2 + 3，只有这三种分解方法，改变素数的顺序如7=3+2+2，不能算另一种方法。

输入描述 Input Description

一个整数N

输出描述 Output Description

一个整数，表示N最多有多少种分解方法

样例输入 Sample Input

20

样例输出 Sample Output

26

数据范围及提示 Data Size & Hint

对于10%的数据 N=1

对于30%的数据 1≤N≤10

对于100%的数据，1≤N≤1000

 

 

//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
int n;
int f[1100][1100];
int zs(int n) {
	for (int i = 2; i <= sqrt(n); i ++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}
int dfs(int n, int t) {
	if (f[n][t] != -1) {
		return f[n][t];
	}
	if (n == 0) {
		return 1;
	}
	int ans = 0;
	for (int i = t; i <= n; i ++) {
		if (zs(i)) {
			ans += dfs(n - i, i);
		}
	}
	return f[n][t] = ans;
}
int main() {
//	freopen ("题目名.in", "r", stdin);
//	freopen ("题目名.out", "w", stdout);
	memset(f, -1, sizeof(f));
	cin >> n;
	cout << dfs(n, 2);
//	fclose (stdin);
//	fclose (stdout);
	return 0;//好习惯！
}

 

为什么50分？

张恩泽在2021-06-06 20:44:29追加了内容

顶！！

张恩泽在2021-06-07 22:24:22追加了内容

我再顶！