Return to factor.c CVS log

Up to [CSRG BSD Unix] / 42BSD / games

Annotation of 42BSD/games/factor.c, revision 1.1.1.1

1.1       root        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: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.