src/factor.c

   1 /* factor -- print factors of n.
   2    Copyright (C) 86, 95, 96, 1997, 1998, 1999, 2000 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 "closeout.h"
  30 #include "error.h"
  31 #include "human.h"
  32 #include "long-options.h"
  33 #include "readtokens.h"
  34 #include "xstrtol.h"
  35
  36 /* The official name of this program (e.g., no `g' prefix).  */
  37 #define PROGRAM_NAME "factor"
  38
  39 #define AUTHORS "Paul Rubin"
  40
  41 /* Token delimiters when reading from a file.  */
  42 #define DELIM "\n\t "
  43
  44 /* FIXME: if this program is ever modified to factor integers larger
  45    than 2^128, this constant (and the algorithm :-) will have to change.  */
  46 #define MAX_N_FACTORS 128
  47
  48 /* The name this program was run with. */
  49 char *program_name;
  50
  51 void
  52 usage (int status)
  53 {
  54   if (status != 0)
  55     fprintf (stderr, _("Try `%s --help' for more information.\n"),
  56              program_name);
  57   else
  58     {
  59       printf (_("\
  60 Usage: %s [NUMBER]...\n\
  61   or:  %s OPTION\n\
  62 "),
  63               program_name, program_name);
  64       printf (_("\
  65 Print factors of each NUMBER; read standard input with no arguments.\n\
  66 \n\
  67   --help      display this help and exit\n\
  68   --version   output version information and exit\n\
  69 \n\
  70   Print the prime factors of all specified integer NUMBERs.  If no arguments\n\
  71   are specified on the command line, they are read from standard input.\n\
  72 "));
  73       puts (_("\nReport bugs to <bug-sh-utils@gnu.org>."));
  74     }
  75   exit (status);
  76 }
  77
  78 /* FIXME: comment */
  79
  80 static int
  81 factor (uintmax_t n0, int max_n_factors, uintmax_t *factors)
  82 {
  83   register uintmax_t n = n0, d, q;
  84   int n_factors = 0;
  85
  86   if (n < 1)
  87     return n_factors;
  88
  89   while (n % 2 == 0)
  90     {
  91       assert (n_factors < max_n_factors);
  92       factors[n_factors++] = 2;
  93       n /= 2;
  94     }
  95
  96   /* The exit condition in the following loop is correct because
  97      any time it is tested one of these 3 conditions holds:
  98       (1) d divides n
  99       (2) n is prime
 100       (3) n is composite but has no factors less than d.
 101      If (1) or (2) obviously the right thing happens.
 102      If (3), then since n is composite it is >= d^2. */
 103
 104   d = 3;
 105   do
 106     {
 107       q = n / d;
 108       while (n == q * d)
 109         {
 110           assert (n_factors < max_n_factors);
 111           factors[n_factors++] = d;
 112           n = q;
 113           q = n / d;
 114         }
 115       d += 2;
 116     }
 117   while (d <= q);
 118
 119   if (n != 1 || n0 == 1)
 120     {
 121       assert (n_factors < max_n_factors);
 122       factors[n_factors++] = n;
 123     }
 124
 125   return n_factors;
 126 }
 127
 128 /* FIXME: comment */
 129
 130 static int
 131 print_factors (const char *s)
 132 {
 133   uintmax_t factors[MAX_N_FACTORS];
 134   uintmax_t n;
 135   int n_factors;
 136   int i;
 137   char buf[LONGEST_HUMAN_READABLE + 1];
 138
 139   if (xstrtoumax (s, NULL, 10, &n, "") != LONGINT_OK)
 140     {
 141       error (0, 0, _("`%s' is not a valid positive integer"), s);
 142       return 1;
 143     }
 144   n_factors = factor (n, MAX_N_FACTORS, factors);
 145   printf ("%s:", human_readable (n, buf, 1, 1));
 146   for (i = 0; i < n_factors; i++)
 147     printf (" %s", human_readable (factors[i], buf, 1, 1));
 148   putchar ('\n');
 149   return 0;
 150 }
 151
 152 static int
 153 do_stdin (void)
 154 {
 155   int fail = 0;
 156   token_buffer tokenbuffer;
 157
 158   init_tokenbuffer (&tokenbuffer);
 159
 160   for (;;)
 161     {
 162       long int token_length;
 163
 164       token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
 165                                 &tokenbuffer);
 166       if (token_length < 0)
 167         break;
 168       fail |= print_factors (tokenbuffer.buffer);
 169     }
 170   free (tokenbuffer.buffer);
 171
 172   return fail;
 173 }
 174
 175 int
 176 main (int argc, char **argv)
 177 {
 178   int fail;
 179
 180   program_name = argv[0];
 181   setlocale (LC_ALL, "");
 182   bindtextdomain (PACKAGE, LOCALEDIR);
 183   textdomain (PACKAGE);
 184
 185   atexit (close_stdout);
 186
 187   parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
 188                       AUTHORS, usage);
 189   /* The above handles --help and --version.
 190      Since there is no other invocation of getopt, handle `--' here.  */
 191   if (argc > 1 && STREQ (argv[1], "--"))
 192     {
 193       --argc;
 194       ++argv;
 195     }
 196
 197   fail = 0;
 198   if (argc == 1)
 199     fail = do_stdin ();
 200   else
 201     {
 202       int i;
 203       for (i = 1; i < argc; i++)
 204         fail |= print_factors (argv[i]);
 205     }
 206   if (fail)
 207     usage (1);
 208
 209   exit (fail);
 210 }