src/factor.c

   1 /* factor -- print factors of n.
   2    Copyright (C) 86, 95, 96, 1997, 1998, 1999 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software Foundation,
  16    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  17
  18 /* Written by Paul Rubin <phr@ocf.berkeley.edu>.
  19    Adapted for GNU, fixed to factor UINT_MAX by Jim Meyering.  */
  20
  21 #include <config.h>
  22 #include <stdio.h>
  23 #include <sys/types.h>
  24
  25 #include <assert.h>
  26 #define NDEBUG 1
  27
  28 #include "system.h"
  29 #include "long-options.h"
  30 #include "error.h"
  31 #include "human.h"
  32 #include "readtokens.h"
  33 #include "xstrtol.h"
  34
  35 /* The official name of this program (e.g., no `g' prefix).  */
  36 #define PROGRAM_NAME "factor"
  37
  38 #define AUTHORS "Paul Rubin"
  39
  40 /* Token delimiters when reading from a file.  */
  41 #define DELIM "\n\t "
  42
  43 /* FIXME: if this program is ever modified to factor integers larger
  44    than 2^128, this constant (and the algorithm :-) will have to change.  */
  45 #define MAX_N_FACTORS 128
  46
  47 /* The name this program was run with. */
  48 char *program_name;
  49
  50 void
  51 usage (int status)
  52 {
  53   if (status != 0)
  54     fprintf (stderr, _("Try `%s --help' for more information.\n"),
  55              program_name);
  56   else
  57     {
  58       printf (_("\
  59 Usage: %s [NUMBER]...\n\
  60   or:  %s OPTION\n\
  61 "),
  62               program_name, program_name);
  63       printf (_("\
  64 Print factors of each NUMBER; read standard input with no arguments.\n\
  65 \n\
  66   --help      display this help and exit\n\
  67   --version   output version information and exit\n\
  68 \n\
  69   Print the prime factors of all specified integer NUMBERs.  If no arguments\n\
  70   are specified on the command line, they are read from standard input.\n\
  71 "));
  72       puts (_("\nReport bugs to <bug-sh-utils@gnu.org>."));
  73     }
  74   exit (status);
  75 }
  76
  77 /* FIXME: comment */
  78
  79 static int
  80 factor (uintmax_t n0, int max_n_factors, uintmax_t *factors)
  81 {
  82   register uintmax_t n = n0, d, q;
  83   int n_factors = 0;
  84
  85   if (n < 1)
  86     return n_factors;
  87
  88   while (n % 2 == 0)
  89     {
  90       assert (n_factors < max_n_factors);
  91       factors[n_factors++] = 2;
  92       n /= 2;
  93     }
  94
  95   /* The exit condition in the following loop is correct because
  96      any time it is tested one of these 3 conditions holds:
  97       (1) d divides n
  98       (2) n is prime
  99       (3) n is composite but has no factors less than d.
 100      If (1) or (2) obviously the right thing happens.
 101      If (3), then since n is composite it is >= d^2. */
 102
 103   d = 3;
 104   do
 105     {
 106       q = n / d;
 107       while (n == q * d)
 108         {
 109           assert (n_factors < max_n_factors);
 110           factors[n_factors++] = d;
 111           n = q;
 112           q = n / d;
 113         }
 114       d += 2;
 115     }
 116   while (d <= q);
 117
 118   if (n != 1 || n0 == 1)
 119     {
 120       assert (n_factors < max_n_factors);
 121       factors[n_factors++] = n;
 122     }
 123
 124   return n_factors;
 125 }
 126
 127 /* FIXME: comment */
 128
 129 static int
 130 print_factors (const char *s)
 131 {
 132   uintmax_t factors[MAX_N_FACTORS];
 133   uintmax_t n;
 134   int n_factors;
 135   int i;
 136   char buf[LONGEST_HUMAN_READABLE + 1];
 137
 138   if (xstrtoumax (s, NULL, 10, &n, "") != LONGINT_OK)
 139     {
 140       error (0, 0, _("`%s' is not a valid positive integer"), s);
 141       return 1;
 142     }
 143   n_factors = factor (n, MAX_N_FACTORS, factors);
 144   printf ("%s:", human_readable (n, buf, 1, 1));
 145   for (i = 0; i < n_factors; i++)
 146     printf (" %s", human_readable (factors[i], buf, 1, 1));
 147   putchar ('\n');
 148   return 0;
 149 }
 150
 151 static int
 152 do_stdin (void)
 153 {
 154   int fail = 0;
 155   token_buffer tokenbuffer;
 156
 157   init_tokenbuffer (&tokenbuffer);
 158
 159   for (;;)
 160     {
 161       long int token_length;
 162
 163       token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
 164                                 &tokenbuffer);
 165       if (token_length < 0)
 166         break;
 167       fail |= print_factors (tokenbuffer.buffer);
 168     }
 169   free (tokenbuffer.buffer);
 170
 171   return fail;
 172 }
 173
 174 int
 175 main (int argc, char **argv)
 176 {
 177   int fail;
 178
 179   program_name = argv[0];
 180   setlocale (LC_ALL, "");
 181   bindtextdomain (PACKAGE, LOCALEDIR);
 182   textdomain (PACKAGE);
 183
 184   parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
 185                       AUTHORS, usage);
 186   /* The above handles --help and --version.
 187      Since there is no other invocation of getopt, handle `--' here.  */
 188   if (argc > 1 && STREQ (argv[1], "--"))
 189     {
 190       --argc;
 191       ++argv;
 192     }
 193
 194   fail = 0;
 195   if (argc == 1)
 196     fail = do_stdin ();
 197   else
 198     {
 199       int i;
 200       for (i = 1; i < argc; i++)
 201         fail |= print_factors (argv[i]);
 202     }
 203   if (fail)
 204     usage (1);
 205
 206   exit (fail);
 207 }