factor/factor.c

   1 /*      $NetBSD: factor.c,v 1.5 1995/03/23 08:28:07 cgd Exp $   */
   2
   3 /*
   4  * Copyright (c) 1989, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Landon Curt Noll.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. All advertising materials mentioning features or use of this software
  19  *    must display the following acknowledgement:
  20  *      This product includes software developed by the University of
  21  *      California, Berkeley and its contributors.
  22  * 4. Neither the name of the University nor the names of its contributors
  23  *    may be used to endorse or promote products derived from this software
  24  *    without specific prior written permission.
  25  *
  26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36  * SUCH DAMAGE.
  37  */
  38
  39 #ifndef lint
  40 static char copyright[] =
  41 "@(#) Copyright (c) 1989, 1993\n\
  42         The Regents of the University of California.  All rights reserved.\n";
  43 #endif /* not lint */
  44
  45 #ifndef lint
  46 #if 0
  47 static char sccsid[] = "@(#)factor.c    8.3 (Berkeley) 3/30/94";
  48 #else
  49 static char rcsid[] = "$NetBSD: factor.c,v 1.5 1995/03/23 08:28:07 cgd Exp $";
  50 #endif
  51 #endif /* not lint */
  52
  53 /*
  54  * factor - factor a number into primes
  55  *
  56  * By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
  57  *
  58  *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
  59  *
  60  * usage:
  61  *      factor [number] ...
  62  *
  63  * The form of the output is:
  64  *
  65  *      number: factor1 factor1 factor2 factor3 factor3 factor3 ...
  66  *
  67  * where factor1 < factor2 < factor3 < ...
  68  *
  69  * If no args are given, the list of numbers are read from stdin.
  70  */
  71
  72 #include <err.h>
  73 #include <ctype.h>
  74 #include <errno.h>
  75 #include <limits.h>
  76 #include <stdio.h>
  77 #include <stdlib.h>
  78
  79 #include "primes.h"
  80
  81 /*
  82  * prime[i] is the (i-1)th prime.
  83  *
  84  * We are able to sieve 2^32-1 because this byte table yields all primes
  85  * up to 65537 and 65537^2 > 2^32-1.
  86  */
  87 extern ubig prime[];
  88 extern ubig *pr_limit;          /* largest prime in the prime array */
  89
  90 void    pr_fact __P((ubig));    /* print factors of a value */
  91 void    usage __P((void));
  92
  93 int
  94 main(argc, argv)
  95         int argc;
  96         char *argv[];
  97 {
  98         ubig val;
  99         int ch;
 100         char *p, buf[100];              /* > max number of digits. */
 101
 102         while ((ch = getopt(argc, argv, "")) != EOF)
 103                 switch (ch) {
 104                 case '?':
 105                 default:
 106                         usage();
 107                 }
 108         argc -= optind;
 109         argv += optind;
 110
 111         /* No args supplied, read numbers from stdin. */
 112         if (argc == 0)
 113                 for (;;) {
 114                         if (fgets(buf, sizeof(buf), stdin) == NULL) {
 115                                 if (ferror(stdin))
 116                                         err(1, "stdin");
 117                                 exit (0);
 118                         }
 119                         for (p = buf; isblank(*p); ++p);
 120                         if (*p == '\n' || *p == '\0')
 121                                 continue;
 122                         if (*p == '-')
 123                                 errx(1, "negative numbers aren't permitted.");
 124                         errno = 0;
 125                         val = strtoul(buf, &p, 10);
 126                         if (errno)
 127                                 err(1, "%s", buf);
 128                         if (*p != '\n')
 129                                 errx(1, "%s: illegal numeric format.", buf);
 130                         pr_fact(val);
 131                 }
 132         /* Factor the arguments. */
 133         else
 134                 for (; *argv != NULL; ++argv) {
 135                         if (argv[0][0] == '-')
 136                                 errx(1, "negative numbers aren't permitted.");
 137                         errno = 0;
 138                         val = strtoul(argv[0], &p, 10);
 139                         if (errno)
 140                                 err(1, "%s", argv[0]);
 141                         if (*p != '\0')
 142                                 errx(1, "%s: illegal numeric format.", argv[0]);
 143                         pr_fact(val);
 144                 }
 145         exit(0);
 146 }
 147
 148 /*
 149  * pr_fact - print the factors of a number
 150  *
 151  * If the number is 0 or 1, then print the number and return.
 152  * If the number is < 0, print -1, negate the number and continue
 153  * processing.
 154  *
 155  * Print the factors of the number, from the lowest to the highest.
 156  * A factor will be printed numtiple times if it divides the value
 157  * multiple times.
 158  *
 159  * Factors are printed with leading tabs.
 160  */
 161 void
 162 pr_fact(val)
 163         ubig val;               /* Factor this value. */
 164 {
 165         ubig *fact;             /* The factor found. */
 166
 167         /* Firewall - catch 0 and 1. */
 168         if (val == 0)           /* Historical practice; 0 just exits. */
 169                 exit(0);
 170         if (val == 1) {
 171                 (void)printf("1: 1\n");
 172                 return;
 173         }
 174
 175         /* Factor value. */
 176         (void)printf("%lu:", val);
 177         for (fact = &prime[0]; val > 1; ++fact) {
 178                 /* Look for the smallest factor. */
 179                 do {
 180                         if (val % (long)*fact == 0)
 181                                 break;
 182                 } while (++fact <= pr_limit);
 183
 184                 /* Watch for primes larger than the table. */
 185                 if (fact > pr_limit) {
 186                         (void)printf(" %lu", val);
 187                         break;
 188                 }
 189
 190                 /* Divide factor out until none are left. */
 191                 do {
 192                         (void)printf(" %lu", *fact);
 193                         val /= (long)*fact;
 194                 } while ((val % (long)*fact) == 0);
 195
 196                 /* Let the user know we're doing something. */
 197                 (void)fflush(stdout);
 198         }
 199         (void)putchar('\n');
 200 }
 201
 202 void
 203 usage()
 204 {
 205         (void)fprintf(stderr, "usage: factor [value ...]\n");
 206         exit (0);
 207 }