2.11BSD#431 - /usr/src/games/factor.c

   1: #ifndef lint
   2: static char sccsid[] = "@(#)factor.c	4.1 (Wollongong) 6/13/83";
   3: #endif
   4: 
   5: /*
   6:  *              factor [ number ]
   7:  *
   8:  * Written to replace factor.s in Bell V7 distribution
   9:  */
  10: 
  11: main(argc, argv)
  12: char    *argv[];
  13: {
  14:     int n;
  15: 
  16:     if (argc >= 2) {
  17:         sscanf(argv[1], "%d", &n);
  18:         if (n > 0)
  19:             printfactors(n);
  20:     } else {
  21:         while (scanf("%d", &n) == 1)
  22:             if (n > 0)
  23:                 printfactors(n);
  24:     }
  25: }
  26: 
  27: /*
  28:  * Print all prime factors of integer n > 0, smallest first, one to a line
  29:  */
  30: printfactors(n)
  31:     register int    n;
  32: {
  33:     register int    prime;
  34: 
  35:     if (n == 1)
  36:         printf("\t1\n");
  37:     else while (n != 1) {
  38:         prime = factor(n);
  39:         printf("\t%d\n", prime);
  40:         n /= prime;
  41:     }
  42: }
  43: 
  44: /*
  45:  * Return smallest prime factor of integer N > 0
  46:  *
  47:  * Algorithm from E.W. Dijkstra (A Discipline of Programming, Chapter 20)
  48:  */
  49: 
  50: int
  51: factor(N)
  52:     int N;
  53: {
  54:     int     p;
  55:     register int    f;
  56:     static struct {
  57:         int hib;
  58:         int val[24];
  59:     } ar;
  60: 
  61:     {   register int    x, y;
  62: 
  63:         ar.hib = -1;
  64:         x = N; y = 2;
  65:         while (x != 0) {
  66:             ar.val[++ar.hib] = x % y;
  67:             x /= y;
  68:             y += 1;
  69:         }
  70:     }
  71: 
  72:     f = 2;
  73: 
  74:     while (ar.val[0] != 0 && ar.hib > 1) {
  75:         register int    i;
  76: 
  77:         f += 1;
  78:         i = 0;
  79:         while (i != ar.hib) {
  80:             register int    j;
  81: 
  82:             j = i + 1;
  83:             ar.val[i] -= j * ar.val[j];
  84:             while (ar.val[i] < 0) {
  85:                 ar.val[i] += f + i;
  86:                 ar.val[j] -= 1;
  87:             }
  88:             i = j;
  89:         }
  90:         while (ar.val[ar.hib] == 0)
  91:             ar.hib--;
  92:     }
  93: 
  94:     if (ar.val[0] == 0)
  95:         p = f;
  96:     else
  97:         p = N;
  98: 
  99:     return(p);
 100: }

Defined functions

Defined variables