factor/factor.c

   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 }