#include int opt_print_all = 0, opt_print_graph = 0; int gcd(int x, int y) { while (x != y && x != 0 && y != 0) if (x < y) y = y % x; else x = x % y; return (x == 0) ? y : x; } int p[100], np; int max_p[100], max_np, max_l, max_t; void try (int l, int n, int t) { if (l == 0 || n <= 1) { if (opt_print_all) { int i, first = 1; printf(" %7d = scm(", t); for (i = 0; i < np; i++) { if (!first) printf(", "); first = 0; printf("%d", p[i]); } for (i = 0; i < l; i++) { if (!first) printf(", "); first = 0; printf("1"); } printf(")\n"); } if (t > max_t) { int i; max_t = t; max_np = np; max_l = l; for (i = 0; i < np; i++) max_p[i] = p[i]; } } else { int i; for (i = n; i >= 1; i--) if (l - i >= 0) { int j, is_rp = 1; for (j = 0; j < np && is_rp; j++) is_rp = gcd(p[j], i) == 1; if (is_rp) { p[np++] = i; try(l - i, i - 1, t * (i / gcd(t, i))); np--; } } } } void main(int argc, char *argv[]) { int i; for (i = 1; i < argc; i++) { char *arg = argv[i]; if (!strcmp(arg, "-all")) opt_print_all = 1; else if (!strcmp(arg, "-graph")) opt_print_graph = 1; else printf("Error: ignore `%s'\n", arg); } for (i = 1; i <= 100; i++) { printf("for %d%s", i, opt_print_all ? "\n" : " | "); np = 0; max_t = 0; try(i, i, 1); if (opt_print_graph) { int k, l; printf(" %9d :", max_t); for (l = max_np - 1, k = 1; k <= i && l >= 0; k++) if (max_p[l] == k) { if (k > 1) printf("%d ", k); l--; } else if (k > 1) printf("%s ", k < 10 ? " " : " "); printf("\n"); } else { int i, first = 1; printf(" %9d = scm(", max_t); for (i = 0; i < max_np; i++) { if (!first) printf(", "); first = 0; printf("%d", max_p[i]); } for (i = 0; i < max_l; i++) { if (!first) printf(", "); first = 0; printf("1"); } printf(")\n"); } } }