Sgu/116

筛出超级素数表后，拿N去背包。

#include <stdio.h>
using namespace std;
#define INF 10000000
 
int notprime[10001], prime[1300], sp[300];
int n, f[10001], g[10001];
 
void make_super_prime()
{
     for (int i = 2; i <= n; ++i)
     {
         if (!notprime[i]) prime[++prime[0]] = i;
         for (int j = 1; j <= prime[0] && i * prime[j] <= n; ++j)
         {
             notprime[i * prime[j]] = 1;
             if (i % prime[j] == 0) break; 
         }
     }
     for (int i = 1; i <= prime[0] && prime[i] <= prime[0]; ++i)
         sp[++sp[0]] = prime[prime[i]];
}
 
void dp()
{
     for (int i = 0; i <= n; ++i) f[i] = INF;
     f[0] = 0;
     for (int i = 0; i < n; ++i)
         for (int j = 1; j <= sp[0] && i + sp[j] <= n; ++j)
             if (f[i] + 1 < f[i + sp[j]])
             {
                f[i + sp[j]] = f[i] + 1;
                g[i + sp[j]] = i;
             }
     if (f[n] == INF) printf("0\n");
     else {
          printf("%d\n", f[n]);
          while (n) {
                printf("%d ", n - g[n]);
                n = g[n];
          }
     }
}
 
int main()
{
    scanf("%d", &n);
    make_super_prime();
    dp();
    return 0;
}
// From FingerSed

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
 
const int size = 10111;
const int inf = 0x3f3f3f3f;
 
int prime[size], check[size], tot = 0;
int ans[size], cnt = 0, dp[size], way[size];
 
void get_prime() {
	memset(check, 0, sizeof(check));
	for (int i = 2; i < size; i++) {
		if (!check[i]) prime[++tot] = i;
		for (int j = i + i; j < size; j += i)
			check[j] = 1;
	}
}
 
void init() {
	get_prime();
        //注意要从2开始。。。刚开始写成1了，，wa哭了
	for (int i = 2; i <= tot; i++) 
		if (check[i] == 0)
			ans[++cnt] = prime[i];
	memset(way, 0, sizeof(way));
	for (int i = 1; i < size; i++)
		dp[i] = inf;
	dp[0] = 0;
}
 
int main() {
	init();
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= cnt; i++) {
		for (int j = ans[i]; j <= n; j++) {
			if (dp[j-ans[i]] + 1 < dp[j]) {
				dp[j] = dp[j-ans[i]] + 1;
				way[j] = j - ans[i];
			}
		}
	}
	if (dp[n] < inf) {
		printf("%d\n", dp[n]);
		int tmp = n;
		for (int i = 1; i <= dp[n] - 1; i++) {
			printf("%d ", tmp - way[tmp]);
			tmp = way[tmp];
		}
		printf("%d\n", tmp);
	} else puts("0");
	return 0;
}