#include <stdio.h>
#include <stdlib.h>
#define xmalloc malloc
#define xfree free
struct node {
void *data;
struct node *left;
struct node *right;
};
void push(struct node **root, void *data, int (*cmp)(void *, void *)) {
struct node *p;
if (!*root) {
p = xmalloc(sizeof(struct node));
p->data = data;
p->left = p->right = NULL;
*root = p;
return;
}
if ((*cmp)(data, (*root)->data) < 0) {
push(&((*root)->left), data, cmp);
} else {
push(&((*root)->right), data, cmp);
}
}
void *pop(struct node **root) {
struct node *p;
void *data;
if (*root == NULL) {
return NULL;
}
if ((*root)->left) {
data = pop(&((*root)->left));
return data;
}
p = *root;
data = p->data;
*root = p->right;
xfree(p);
return data;
}
#define N 100000
#define TABSIZE 10000
static int primeS[N];
int maketable(void) {
int n, i, r, q, idx;
primeS[0] = 2;
primeS[1] = 3;
idx = 2;
for (n = 4; n < N; n++) {
i = 0;
do {
r = n % primeS[i];
if (r == 0)
break;
q = n / primeS[i];
i++;
} while (primeS[i] < q);
if (r > 0) {
printf("prime: %d\n", n);
primeS[idx] = n;
idx++;
if (idx > TABSIZE) {
fprintf(stderr, "table size is too small, aborted. idx = %d\n", idx);
exit(-1);
}
}
}
return idx;
}
struct data {
int n;
double s;
int u, v, w;
};
int cmp(struct data *a, struct data *b) {
return (a->s > b->s) ? -1 : 1;
}
int main() {
int n;
int i, u, v, w;
int t;
struct data *p;
struct node *root;
n = maketable();
printf("n = %d\n", n);
for (i = 2; i < N; i++) {
root = NULL;
for (u = 0; primeS[u] <= i; u++) {
for (v = u; primeS[v] <= i - primeS[u]; v++) {
t = i - primeS[u] - primeS[v];
if (t < 2)
break;
for (w = v; primeS[w] <= t; w++) {
if (t == primeS[w]) {
p = xmalloc(sizeof(struct data));
p->u = u; p->v = v; p->w = w;
p->s = (double)primeS[u] * primeS[v] * primeS[w];
p->n = i;
push(&root, p, (int (*)(void *, void *))cmp);
}
}
}
}
if ((p = pop(&root)) != NULL) {
printf("%d = %d + %d + %d\n", p->n, primeS[p->u], primeS[p->v], primeS[p->w]);
xfree(p);
}
while ((p = pop(&root)) != NULL) {
/* printf("%d = %d + %d + %d\n", p->n, primeS[p->u], primeS[p->v], primeS[p->w]); */
xfree(p);
}
}
return 0;
}