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