Return to factor.c CVS log

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

Annotation of 42BSD/games/factor.c, revision 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.