Advertisement
Guest User

Untitled

a guest
Oct 13th, 2012
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.29 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAX 1000
  5.  
  6. int prevprime[MAX];
  7.  
  8. int isprime(int n) {
  9.     int i;
  10.     if (n < 2) return 0;
  11.     for(i = 2; i*i <= n; i++) {
  12.         if (n % i == 0) return 0;
  13.     }
  14.     return 1;
  15. }
  16. void init_prevprime() {
  17.     int i;
  18.     prevprime[0] = -1;
  19.     for(i = 1; i < MAX; i++) {
  20.         prevprime[i] = isprime(i-1) ? i-1 : prevprime[i-1];
  21.     }
  22. }
  23. void findsums(int n) {
  24.     int seq[MAX/2];
  25.     int nseq = 0;
  26.     int p = prevprime[n+1];
  27.     int nsols = 0;
  28.     int i;
  29.     for(;;) {
  30.         n -= p;
  31.         seq[nseq++] = p;
  32.         if (n == 0) {
  33.             printf("%d:",++nsols);
  34.             for(i = 0; i < nseq; i++) {
  35.                 printf(" %d", seq[i]);
  36.             }
  37.             putchar('\n');
  38.         }
  39.         if (n <= 0) {
  40.             p = -1;
  41.         }
  42.         while (p < 0 && nseq > 0) {
  43.             p = seq[--nseq];
  44.             n += p;
  45.             p = prevprime[p];
  46.         }
  47.         if (p < 0 && nseq <= 0) {
  48.             break;
  49.         }
  50.     }
  51.     printf("Total %d sums for %d\n", nsols, n);
  52. }
  53.  
  54. int main(int argc, char **argv) {
  55.     (void)argc;
  56.     init_prevprime();
  57.     while(argv[1]) {
  58.         int n = atoi(argv[1]);
  59.         printf("Sums for %d:\n", n);
  60.         findsums(n);
  61.         argv++;
  62.     }
  63.     return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement