Return to factor.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / games / factor

Annotation of 43BSDReno/games/factor/factor.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1989 The Regents of the University of California.
        !             3:  * All rights reserved.
        !             4:  *
        !             5:  * This code is derived from software contributed to Berkeley by
        !             6:  * Landon Curt Noll.
        !             7:  *
        !             8:  * Redistribution and use in source and binary forms are permitted
        !             9:  * provided that: (1) source distributions retain this entire copyright
        !            10:  * notice and comment, and (2) distributions including binaries display
        !            11:  * the following acknowledgement:  ``This product includes software
        !            12:  * developed by the University of California, Berkeley and its contributors''
        !            13:  * in the documentation or other materials provided with the distribution
        !            14:  * and in all advertising materials mentioning features or use of this
        !            15:  * software. Neither the name of the University nor the names of its
        !            16:  * contributors may be used to endorse or promote products derived
        !            17:  * from this software without specific prior written permission.
        !            18:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
        !            19:  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
        !            20:  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
        !            21:  */
        !            22: 
        !            23: #ifndef lint
        !            24: char copyright[] =
        !            25: "@(#) Copyright (c) 1989 The Regents of the University of California.\n\
        !            26:  All rights reserved.\n";
        !            27: #endif /* not lint */
        !            28: 
        !            29: #ifndef lint
        !            30: static char sccsid[] = "@(#)factor.c   4.4 (Berkeley) 6/1/90";
        !            31: #endif /* not lint */
        !            32: 
        !            33: /*
        !            34:  * factor - factor a number into primes
        !            35:  *
        !            36:  * By: Landon Curt Noll   [email protected],   ...!{sun,tolsoft}!hoptoad!chongo
        !            37:  *
        !            38:  *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
        !            39:  *
        !            40:  * usage:
        !            41:  *     factor [number] ...
        !            42:  *
        !            43:  * The form of the output is:
        !            44:  *
        !            45:  *     number: factor1 factor1 factor2 factor3 factor3 factor3 ...
        !            46:  *
        !            47:  * where factor1 < factor2 < factor3 < ...
        !            48:  *
        !            49:  * If no args are given, the list of numbers are read from stdin.
        !            50:  */
        !            51: 
        !            52: #include <stdio.h>
        !            53: #include <ctype.h>
        !            54: #include "primes.h"
        !            55: 
        !            56: /*
        !            57:  * prime[i] is the (i-1)th prime.
        !            58:  *
        !            59:  * We are able to sieve 2^32-1 because this byte table yields all primes 
        !            60:  * up to 65537 and 65537^2 > 2^32-1.
        !            61:  */
        !            62: extern ubig prime[];
        !            63: extern ubig *pr_limit; /* largest prime in the prime array */
        !            64: 
        !            65: #define MAX_LINE 255   /* max line allowed on stdin */
        !            66: 
        !            67: void pr_fact();                /* print factors of a value */
        !            68: long small_fact();     /* find smallest factor of a value */
        !            69: char *read_num_buf();  /* read a number buffer */
        !            70: char *program;         /* name of this program */
        !            71: 
        !            72: main(argc, argv)
        !            73:        int argc;       /* arg count */
        !            74:        char *argv[];   /* the args */
        !            75: {
        !            76:        int arg;        /* which arg to factor */
        !            77:        long val;       /* the value to factor */
        !            78:        char buf[MAX_LINE+1];   /* input buffer */
        !            79: 
        !            80:        /* parse args */
        !            81:        program = argv[0];
        !            82:        if (argc >= 2) {
        !            83: 
        !            84:                /* factor each arg */
        !            85:                for (arg=1; arg < argc; ++arg) {
        !            86: 
        !            87:                        /* process the buffer */
        !            88:                        if (read_num_buf(NULL, argv[arg]) == NULL) {
        !            89:                                fprintf(stderr, "%s: ouch\n", program);
        !            90:                                exit(1);
        !            91:                        }
        !            92: 
        !            93:                        /* factor the argument */
        !            94:                        if (sscanf(argv[arg], "%ld", &val) == 1) {
        !            95:                                pr_fact(val);
        !            96:                        } else {
        !            97:                                fprintf(stderr, "%s: ouch\n", program);
        !            98:                                exit(1);
        !            99:                        }
        !           100:                }
        !           101: 
        !           102:        /* no args supplied, read numbers from stdin */
        !           103:        } else {
        !           104:                /*
        !           105:                 * read asciii numbers from input
        !           106:                 */
        !           107:                while (read_num_buf(stdin, buf) != NULL) {
        !           108: 
        !           109:                        /* factor the argument */
        !           110:                        if (sscanf(buf, "%ld", &val) == 1) {
        !           111:                                pr_fact(val);
        !           112:                        }
        !           113:                }
        !           114:        }
        !           115:        exit(0);
        !           116: }
        !           117: 
        !           118: /*
        !           119:  * read_num_buf - read a number buffer from a stream
        !           120:  *
        !           121:  * Read a number on a line of the form:
        !           122:  *
        !           123:  *     ^[ \t]*\([+-]?[0-9][0-9]\)*.*$
        !           124:  *
        !           125:  * where ? is a 1-or-0 operator and the number is within \( \).
        !           126:  *
        !           127:  * If does not match the above pattern, it is ignored and a new
        !           128:  * line is read.  If the number is too large or small, we will
        !           129:  * print ouch and read a new line.
        !           130:  *
        !           131:  * We have to be very careful on how we check the magnitude of the
        !           132:  * input.  We can not use numeric checks because of the need to
        !           133:  * check values against maximum numeric values.
        !           134:  *
        !           135:  * This routine will return a line containing a ascii number between
        !           136:  * NEG_SEMIBIG and SEMIBIG, or it will return NULL.
        !           137:  *
        !           138:  * If the stream is NULL then buf will be processed as if were
        !           139:  * a single line stream.
        !           140:  *
        !           141:  * returns:
        !           142:  *     char *  pointer to leading digit, + or -
        !           143:  *     NULL    EOF or error
        !           144:  */
        !           145: char *
        !           146: read_num_buf(input, buf)
        !           147:        FILE *input;            /* input stream or NULL */
        !           148:        char *buf;              /* input buffer */
        !           149: {
        !           150:        static char limit[MAX_LINE+1];  /* ascii value of SEMIBIG */
        !           151:        static int limit_len;           /* digit count of limit */
        !           152:        static char neg_limit[MAX_LINE+1];      /* value of NEG_SEMIBIG */
        !           153:        static int neg_limit_len;               /* digit count of neg_limit */
        !           154:        int len;                        /* digits in input (excluding +/-) */
        !           155:        char *s;        /* line start marker */
        !           156:        char *d;        /* first digit, skip +/- */
        !           157:        char *p;        /* scan pointer */
        !           158:        char *z;        /* zero scan pointer */
        !           159: 
        !           160:        /* form the ascii value of SEMIBIG if needed */
        !           161:        if (!isascii(limit[0]) || !isdigit(limit[0])) {
        !           162:                sprintf(limit, "%ld", SEMIBIG);
        !           163:                limit_len = strlen(limit);
        !           164:                sprintf(neg_limit, "%ld", NEG_SEMIBIG);
        !           165:                neg_limit_len = strlen(neg_limit)-1;    /* exclude - */
        !           166:        }
        !           167:        
        !           168:        /*
        !           169:         * the search for a good line
        !           170:         */
        !           171:        if (input != NULL && fgets(buf, MAX_LINE, input) == NULL) {
        !           172:                /* error or EOF */
        !           173:                return NULL;
        !           174:        }
        !           175:        do {
        !           176: 
        !           177:                /* ignore leading whitespace */
        !           178:                for (s=buf; *s && s < buf+MAX_LINE; ++s) {
        !           179:                        if (!isascii(*s) || !isspace(*s)) {
        !           180:                                break;
        !           181:                        }
        !           182:                }
        !           183: 
        !           184:                /* skip over any leading + or - */
        !           185:                if (*s == '+' || *s == '-') {
        !           186:                        d = s+1;
        !           187:                } else {
        !           188:                        d = s;
        !           189:                }
        !           190: 
        !           191:                /* note leading zeros */
        !           192:                for (z=d; *z && z < buf+MAX_LINE; ++z) {
        !           193:                        if (*z != '0') {
        !           194:                                break;
        !           195:                        }
        !           196:                }
        !           197: 
        !           198:                /* scan for the first non-digit */
        !           199:                for (p=d; *p && p < buf+MAX_LINE; ++p) {
        !           200:                        if (!isascii(*p) || !isdigit(*p)) {
        !           201:                                break;
        !           202:                        }
        !           203:                }
        !           204: 
        !           205:                /* ignore empty lines */
        !           206:                if (p == d) {
        !           207:                        continue;
        !           208:                }
        !           209:                *p = '\0';
        !           210: 
        !           211:                /* object if too many digits */
        !           212:                len = strlen(z);
        !           213:                len = (len<=0) ? 1 : len;
        !           214:                if (*s == '-') {
        !           215:                        /* accept if digit count is below limit */
        !           216:                        if (len < neg_limit_len) {
        !           217:                                /* we have good input */
        !           218:                                return s;
        !           219: 
        !           220:                        /* reject very large numbers */
        !           221:                        } else if (len > neg_limit_len) {
        !           222:                                fprintf(stderr, "%s: ouch\n", program);
        !           223:                                exit(1);
        !           224: 
        !           225:                        /* carefully check against near limit numbers */
        !           226:                        } else if (strcmp(z, neg_limit+1) > 0) {
        !           227:                                fprintf(stderr, "%s: ouch\n", program);
        !           228:                                exit(1);
        !           229:                        }
        !           230:                        /* number is near limit, but is under it */
        !           231:                        return s;
        !           232:                
        !           233:                } else {
        !           234:                        /* accept if digit count is below limit */
        !           235:                        if (len < limit_len) {
        !           236:                                /* we have good input */
        !           237:                                return s;
        !           238: 
        !           239:                        /* reject very large numbers */
        !           240:                        } else if (len > limit_len) {
        !           241:                                fprintf(stderr, "%s: ouch\n", program);
        !           242:                                exit(1);
        !           243: 
        !           244:                        /* carefully check against near limit numbers */
        !           245:                        } else if (strcmp(z, limit) > 0) {
        !           246:                                fprintf(stderr, "%s: ouch\n", program);
        !           247:                                exit(1);
        !           248:                        }
        !           249:                        /* number is near limit, but is under it */
        !           250:                        return s;
        !           251:                }
        !           252:        } while (input != NULL && fgets(buf, MAX_LINE, input) != NULL);
        !           253: 
        !           254:        /* error or EOF */
        !           255:        return NULL;
        !           256: }
        !           257: 
        !           258: 
        !           259: /*
        !           260:  * pr_fact - print the factors of a number
        !           261:  *
        !           262:  * If the number is 0 or 1, then print the number and return.
        !           263:  * If the number is < 0, print -1, negate the number and continue
        !           264:  * processing.
        !           265:  *
        !           266:  * Print the factors of the number, from the lowest to the highest.
        !           267:  * A factor will be printed numtiple times if it divides the value
        !           268:  * multiple times.
        !           269:  *
        !           270:  * Factors are printed with leading tabs.
        !           271:  */
        !           272: void
        !           273: pr_fact(val)
        !           274:        long val;       /* factor this value */
        !           275: {
        !           276:        ubig *fact;     /* the factor found */
        !           277: 
        !           278:        /* firewall - catch 0 and 1 */
        !           279:        switch (val) {
        !           280:        case -2147483648:
        !           281:                /* avoid negation problems */
        !           282:                puts("-2147483648: -1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2\n");
        !           283:                return;
        !           284:        case -1:
        !           285:                puts("-1: -1\n");
        !           286:                return;
        !           287:        case 0:
        !           288:                exit(0);
        !           289:        case 1:
        !           290:                puts("1: 1\n");
        !           291:                return;
        !           292:        default:
        !           293:                if (val < 0) {
        !           294:                        val = -val;
        !           295:                        printf("%ld: -1", val);
        !           296:                } else {
        !           297:                        printf("%ld:", val);
        !           298:                }
        !           299:                fflush(stdout);
        !           300:                break;
        !           301:        }
        !           302: 
        !           303:        /*
        !           304:         * factor value
        !           305:         */
        !           306:        fact = &prime[0];
        !           307:        while (val > 1) {
        !           308: 
        !           309:                /* look for the smallest factor */
        !           310:                do {
        !           311:                        if (val%(long)*fact == 0) {
        !           312:                                break;
        !           313:                        }
        !           314:                } while (++fact <= pr_limit);
        !           315: 
        !           316:                /* watch for primes larger than the table */
        !           317:                if (fact > pr_limit) {
        !           318:                        printf(" %ld\n", val);
        !           319:                        return;
        !           320:                }
        !           321: 
        !           322:                /* divide factor out until none are left */
        !           323:                do {
        !           324:                        printf(" %ld", *fact);
        !           325:                        val /= (long)*fact;
        !           326:                } while ((val % (long)*fact) == 0);
        !           327:                fflush(stdout);
        !           328:                ++fact;
        !           329:        }
        !           330:        putchar('\n');
        !           331:        return;
        !           332: }

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