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[] = "from: @(#)factor.c    4.4 (Berkeley) 6/1/90";*/
  45 static char rcsid[] = "$Id: factor.c,v 1.4 1994/03/03 03:07:24 deraadt Exp $";
  46 #endif /* not lint */
  47
  48 /*
  49  * factor - factor a number into primes
  50  *
  51  * By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
  52  *
  53  *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
  54  *
  55  * usage:
  56  *      factor [number] ...
  57  *
  58  * The form of the output is:
  59  *
  60  *      number: factor1 factor1 factor2 factor3 factor3 factor3 ...
  61  *
  62  * where factor1 < factor2 < factor3 < ...
  63  *
  64  * If no args are given, the list of numbers are read from stdin.
  65  */
  66
  67 #include <stdio.h>
  68 #include <limits.h>
  69 #include <ctype.h>
  70 #include "primes.h"
  71
  72 /*
  73  * prime[i] is the (i-1)th prime.
  74  *
  75  * We are able to sieve 2^32-1 because this byte table yields all primes
  76  * up to 65537 and 65537^2 > 2^32-1.
  77  */
  78 extern ubig prime[];
  79 extern ubig *pr_limit;  /* largest prime in the prime array */
  80
  81 #define MAX_LINE 255    /* max line allowed on stdin */
  82
  83 void pr_fact();         /* print factors of a value */
  84 long small_fact();      /* find smallest factor of a value */
  85 char *read_num_buf();   /* read a number buffer */
  86 char *program;          /* name of this program */
  87
  88 main(argc, argv)
  89         int argc;       /* arg count */
  90         char *argv[];   /* the args */
  91 {
  92         int arg;        /* which arg to factor */
  93         long val;       /* the value to factor */
  94         char buf[MAX_LINE+1];   /* input buffer */
  95
  96         /* parse args */
  97         program = argv[0];
  98         if (argc >= 2) {
  99
 100                 /* factor each arg */
 101                 for (arg=1; arg < argc; ++arg) {
 102
 103                         /* process the buffer */
 104                         if (read_num_buf(NULL, argv[arg]) == NULL) {
 105                                 fprintf(stderr, "%s: ouch\n", program);
 106                                 exit(1);
 107                         }
 108
 109                         /* factor the argument */
 110                         if (sscanf(argv[arg], "%ld", &val) == 1) {
 111                                 pr_fact(val);
 112                         } else {
 113                                 fprintf(stderr, "%s: ouch\n", program);
 114                                 exit(1);
 115                         }
 116                 }
 117
 118         /* no args supplied, read numbers from stdin */
 119         } else {
 120                 /*
 121                  * read asciii numbers from input
 122                  */
 123                 while (read_num_buf(stdin, buf) != NULL) {
 124
 125                         /* factor the argument */
 126                         if (sscanf(buf, "%ld", &val) == 1) {
 127                                 pr_fact(val);
 128                         }
 129                 }
 130         }
 131         exit(0);
 132 }
 133
 134 /*
 135  * read_num_buf - read a number buffer from a stream
 136  *
 137  * Read a number on a line of the form:
 138  *
 139  *      ^[ \t]*\([+-]?[0-9][0-9]\)*.*$
 140  *
 141  * where ? is a 1-or-0 operator and the number is within \( \).
 142  *
 143  * If does not match the above pattern, it is ignored and a new
 144  * line is read.  If the number is too large or small, we will
 145  * print ouch and read a new line.
 146  *
 147  * We have to be very careful on how we check the magnitude of the
 148  * input.  We can not use numeric checks because of the need to
 149  * check values against maximum numeric values.
 150  *
 151  * This routine will return a line containing a ascii number between
 152  * NEG_SEMIBIG and SEMIBIG, or it will return NULL.
 153  *
 154  * If the stream is NULL then buf will be processed as if were
 155  * a single line stream.
 156  *
 157  * returns:
 158  *      char *  pointer to leading digit, + or -
 159  *      NULL    EOF or error
 160  */
 161 char *
 162 read_num_buf(input, buf)
 163         FILE *input;            /* input stream or NULL */
 164         char *buf;              /* input buffer */
 165 {
 166         static char limit[MAX_LINE+1];  /* ascii value of SEMIBIG */
 167         static int limit_len;           /* digit count of limit */
 168         static char neg_limit[MAX_LINE+1];      /* value of NEG_SEMIBIG */
 169         static int neg_limit_len;               /* digit count of neg_limit */
 170         int len;                        /* digits in input (excluding +/-) */
 171         char *s;        /* line start marker */
 172         char *d;        /* first digit, skip +/- */
 173         char *p;        /* scan pointer */
 174         char *z;        /* zero scan pointer */
 175
 176         /* form the ascii value of SEMIBIG if needed */
 177         if (!isascii(limit[0]) || !isdigit(limit[0])) {
 178                 sprintf(limit, "%ld", SEMIBIG);
 179                 limit_len = strlen(limit);
 180                 sprintf(neg_limit, "%ld", NEG_SEMIBIG);
 181                 neg_limit_len = strlen(neg_limit)-1;    /* exclude - */
 182         }
 183
 184         /*
 185          * the search for a good line
 186          */
 187         if (input != NULL && fgets(buf, MAX_LINE, input) == NULL) {
 188                 /* error or EOF */
 189                 return NULL;
 190         }
 191         do {
 192
 193                 /* ignore leading whitespace */
 194                 for (s=buf; *s && s < buf+MAX_LINE; ++s) {
 195                         if (!isascii(*s) || !isspace(*s)) {
 196                                 break;
 197                         }
 198                 }
 199
 200                 /* skip over any leading + or - */
 201                 if (*s == '+' || *s == '-') {
 202                         d = s+1;
 203                 } else {
 204                         d = s;
 205                 }
 206
 207                 /* note leading zeros */
 208                 for (z=d; *z && z < buf+MAX_LINE; ++z) {
 209                         if (*z != '0') {
 210                                 break;
 211                         }
 212                 }
 213
 214                 /* scan for the first non-digit */
 215                 for (p=d; *p && p < buf+MAX_LINE; ++p) {
 216                         if (!isascii(*p) || !isdigit(*p)) {
 217                                 break;
 218                         }
 219                 }
 220
 221                 /* ignore empty lines */
 222                 if (p == d) {
 223                         continue;
 224                 }
 225                 *p = '\0';
 226
 227                 /* object if too many digits */
 228                 len = strlen(z);
 229                 len = (len<=0) ? 1 : len;
 230                 if (*s == '-') {
 231                         /* accept if digit count is below limit */
 232                         if (len < neg_limit_len) {
 233                                 /* we have good input */
 234                                 return s;
 235
 236                         /* reject very large numbers */
 237                         } else if (len > neg_limit_len) {
 238                                 fprintf(stderr, "%s: ouch\n", program);
 239                                 exit(1);
 240
 241                         /* carefully check against near limit numbers */
 242                         } else if (strcmp(z, neg_limit+1) > 0) {
 243                                 fprintf(stderr, "%s: ouch\n", program);
 244                                 exit(1);
 245                         }
 246                         /* number is near limit, but is under it */
 247                         return s;
 248
 249                 } else {
 250                         /* accept if digit count is below limit */
 251                         if (len < limit_len) {
 252                                 /* we have good input */
 253                                 return s;
 254
 255                         /* reject very large numbers */
 256                         } else if (len > limit_len) {
 257                                 fprintf(stderr, "%s: ouch\n", program);
 258                                 exit(1);
 259
 260                         /* carefully check against near limit numbers */
 261                         } else if (strcmp(z, limit) > 0) {
 262                                 fprintf(stderr, "%s: ouch\n", program);
 263                                 exit(1);
 264                         }
 265                         /* number is near limit, but is under it */
 266                         return s;
 267                 }
 268         } while (input != NULL && fgets(buf, MAX_LINE, input) != NULL);
 269
 270         /* error or EOF */
 271         return NULL;
 272 }
 273
 274
 275 /*
 276  * pr_fact - print the factors of a number
 277  *
 278  * If the number is 0 or 1, then print the number and return.
 279  * If the number is < 0, print -1, negate the number and continue
 280  * processing.
 281  *
 282  * Print the factors of the number, from the lowest to the highest.
 283  * A factor will be printed numtiple times if it divides the value
 284  * multiple times.
 285  *
 286  * Factors are printed with leading tabs.
 287  */
 288 void
 289 pr_fact(val)
 290         long val;       /* factor this value */
 291 {
 292         ubig *fact;     /* the factor found */
 293
 294         /* firewall - catch 0 and 1 */
 295         switch (val) {
 296         case -(2147483648U):
 297                 /* avoid negation problems */
 298                 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");
 299                 return;
 300         case -1:
 301                 puts("-1: -1\n");
 302                 return;
 303         case 0:
 304                 exit(0);
 305         case 1:
 306                 puts("1: 1\n");
 307                 return;
 308         default:
 309                 if (val < 0) {
 310                         val = -val;
 311                         printf("%ld: -1", val);
 312                 } else {
 313                         printf("%ld:", val);
 314                 }
 315                 fflush(stdout);
 316                 break;
 317         }
 318
 319         /*
 320          * factor value
 321          */
 322         fact = &prime[0];
 323         while (val > 1) {
 324
 325                 /* look for the smallest factor */
 326                 do {
 327                         if (val%(long)*fact == 0) {
 328                                 break;
 329                         }
 330                 } while (++fact <= pr_limit);
 331
 332                 /* watch for primes larger than the table */
 333                 if (fact > pr_limit) {
 334                         printf(" %ld\n", val);
 335                         return;
 336                 }
 337
 338                 /* divide factor out until none are left */
 339                 do {
 340                         printf(" %ld", *fact);
 341                         val /= (long)*fact;
 342                 } while ((val % (long)*fact) == 0);
 343                 fflush(stdout);
 344                 ++fact;
 345         }
 346         putchar('\n');
 347         return;
 348 }