#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
int prevprime[MAX];
int isprime(int n) {
int i;
if (n < 2) return 0;
for(i = 2; i*i <= n; i++) {
if (n % i == 0) return 0;
}
return 1;
}
void init_prevprime() {
int i;
prevprime[0] = -1;
for(i = 1; i < MAX; i++) {
prevprime[i] = isprime(i-1) ? i-1 : prevprime[i-1];
}
}
void findsums(int n) {
int seq[MAX/2];
int nseq = 0;
int p = prevprime[n+1];
int nsols = 0;
int i;
for(;;) {
n -= p;
seq[nseq++] = p;
if (n == 0) {
printf("%d:",++nsols);
for(i = 0; i < nseq; i++) {
printf(" %d", seq[i]);
}
putchar('\n');
}
if (n <= 0) {
p = -1;
}
while (p < 0 && nseq > 0) {
p = seq[--nseq];
n += p;
p = prevprime[p];
}
if (p < 0 && nseq <= 0) {
break;
}
}
printf("Total %d sums for %d\n", nsols, n);
}
int main(int argc, char **argv) {
(void)argc;
init_prevprime();
while(argv[1]) {
int n = atoi(argv[1]);
printf("Sums for %d:\n", n);
findsums(n);
argv++;
}
return 0;
}