factor/factor.c

   1 /*      $NetBSD: factor.c,v 1.8 1998/09/13 15:27:27 hubertf 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 #include <sys/cdefs.h>
  40 #ifndef lint
  41 __COPYRIGHT("@(#) 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.4 (Berkeley) 5/4/95";
  48 #else
  49 __RCSID("$NetBSD: factor.c,v 1.8 1998/09/13 15:27:27 hubertf 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 #include <unistd.h>
  79
  80 #include "primes.h"
  81
  82 /*
  83  * prime[i] is the (i-1)th prime.
  84  *
  85  * We are able to sieve 2^32-1 because this byte table yields all primes
  86  * up to 65537 and 65537^2 > 2^32-1.
  87  */
  88 extern ubig prime[];
  89 extern ubig *pr_limit;          /* largest prime in the prime array */
  90
  91 int     main __P((int, char *[]));
  92 void    pr_fact __P((ubig));    /* print factors of a value */
  93 void    usage __P((void)) __attribute__((__noreturn__));
  94
  95 int
  96 main(argc, argv)
  97         int argc;
  98         char *argv[];
  99 {
 100         ubig val;
 101         int ch;
 102         char *p, buf[100];              /* > max number of digits. */
 103
 104         while ((ch = getopt(argc, argv, "")) != -1)
 105                 switch (ch) {
 106                 case '?':
 107                 default:
 108                         usage();
 109                 }
 110         argc -= optind;
 111         argv += optind;
 112
 113         /* No args supplied, read numbers from stdin. */
 114         if (argc == 0)
 115                 for (;;) {
 116                         if (fgets(buf, sizeof(buf), stdin) == NULL) {
 117                                 if (ferror(stdin))
 118                                         err(1, "stdin");
 119                                 exit (0);
 120                         }
 121                         for (p = buf; isblank(*p); ++p);
 122                         if (*p == '\n' || *p == '\0')
 123                                 continue;
 124                         if (*p == '-')
 125                                 errx(1, "negative numbers aren't permitted.");
 126                         errno = 0;
 127                         val = strtoul(buf, &p, 10);
 128                         if (errno)
 129                                 err(1, "%s", buf);
 130                         if (*p != '\n')
 131                                 errx(1, "%s: illegal numeric format.", buf);
 132                         pr_fact(val);
 133                 }
 134         /* Factor the arguments. */
 135         else
 136                 for (; *argv != NULL; ++argv) {
 137                         if (argv[0][0] == '-')
 138                                 errx(1, "negative numbers aren't permitted.");
 139                         errno = 0;
 140                         val = strtoul(argv[0], &p, 10);
 141                         if (errno)
 142                                 err(1, "%s", argv[0]);
 143                         if (*p != '\0')
 144                                 errx(1, "%s: illegal numeric format.", argv[0]);
 145                         pr_fact(val);
 146                 }
 147         exit(0);
 148 }
 149
 150 /*
 151  * pr_fact - print the factors of a number
 152  *
 153  * If the number is 0 or 1, then print the number and return.
 154  * If the number is < 0, print -1, negate the number and continue
 155  * processing.
 156  *
 157  * Print the factors of the number, from the lowest to the highest.
 158  * A factor will be printed numtiple times if it divides the value
 159  * multiple times.
 160  *
 161  * Factors are printed with leading tabs.
 162  */
 163 void
 164 pr_fact(val)
 165         ubig val;               /* Factor this value. */
 166 {
 167         ubig *fact;             /* The factor found. */
 168
 169         /* Firewall - catch 0 and 1. */
 170         if (val == 0)           /* Historical practice; 0 just exits. */
 171                 exit(0);
 172         if (val == 1) {
 173                 (void)printf("1: 1\n");
 174                 return;
 175         }
 176
 177         /* Factor value. */
 178         (void)printf("%lu:", val);
 179         for (fact = &prime[0]; val > 1; ++fact) {
 180                 /* Look for the smallest factor. */
 181                 do {
 182                         if (val % (long)*fact == 0)
 183                                 break;
 184                 } while (++fact <= pr_limit);
 185
 186                 /* Watch for primes larger than the table. */
 187                 if (fact > pr_limit) {
 188                         (void)printf(" %lu", val);
 189                         break;
 190                 }
 191
 192                 /* Divide factor out until none are left. */
 193                 do {
 194                         (void)printf(" %lu", *fact);
 195                         val /= (long)*fact;
 196                 } while ((val % (long)*fact) == 0);
 197
 198                 /* Let the user know we're doing something. */
 199                 (void)fflush(stdout);
 200         }
 201         (void)putchar('\n');
 202 }
 203
 204 void
 205 usage()
 206 {
 207         (void)fprintf(stderr, "usage: factor [value ...]\n");
 208         exit (0);
 209 }