问题标题: 酷町堂：3012 素数入门

3012   素数入门

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

题目描述 Description

素数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。现给定一个正整数n，求将其分解成若干个素数之和的方案总数。

输入描述 Input Description

一行：一个正整数n

输出描述 Output Description

一行：一个整数表示方案总数

样例输入 Sample Input

7

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

【样例解释】

7=7 7=2+5

7=2+2+3

【福利数据】

【输入】 20

【输出】 26

【数据范围及约定】

对于30%的数据 1<=n<=10

对于100%的数据，1<=n<=10^3

//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
int cnt;
int f[50000];
bool is_prime(int n) {
	if (n == 1) {
		return false;
	}
	for (int i = 2; i <= sqrt(n); i ++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}
int prime(int n) {
	int c; 
	for (int i = 1; i <= n; i ++) {
		if (is_prime(i)) {
			c ++;
		}
	}
}
int main() {
//	freopen ("题目名.in", "r", stdin);
//	freopen ("题目名.out", "w", stdout);
	cin >> n;
	int cnt = prime(n);
	for (int i = 2; i <= cnt; i ++) {
		for (int j = i; j <= n; j ++) {
			f[j] = max(f[j - i] + 1, f[j]);
		}
	}
	cout << f[n];
//	fclose (stdin);
//	fclose (stdout);
	return 0;//好习惯！
}

WA了，20分

张恩泽在2021-08-08 17:18:54追加了内容

只要这道题写出来了，那1105也就写出来了，几乎一样

张恩泽在2021-08-08 17:18:58追加了内容

只要这道题写出来了，那1105也就写出来了，几乎一样

张恩泽在2021-08-15 08:22:51追加了内容

//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
int cnt;
int f[50000];
bool is_prime(int n) {
	if (n == 1) {
		return false;
	}
	for (int i = 2; i <= sqrt(n); i ++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}
int prime(int n) {
	int c; 
	for (int i = 1; i <= n; i ++) {
		if (is_prime(i)) {
			c ++;
		}
	}
}
int main() {
//	freopen ("题目名.in", "r", stdin);
//	freopen ("题目名.out", "w", stdout);
	cin >> n;
	int cnt = prime(n);
	for (int i = 2; i <= cnt; i ++) {
		for (int j = i; j <= n; j ++) {
			if (is_prime(i)) {
				f[j] = max(f[j - i] + 1, f[j]);
			}
		}
	}
	cout << f[n];
//	fclose (stdin);
//	fclose (stdout);
	return 0;//好习惯！
}

又判断了一下i是不是质数，可还是不对