src/factor.c

   1 /* factor -- print prime factors of n.
   2    Copyright (C) 86, 1995-2003 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 "error.h"
  30 #include "inttostr.h"
  31 #include "long-options.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 trial divisor increment wheel.  Use it to skip over divisors that
  48    are composites of 2, 3, 5, 7, or 11.  The part from WHEEL_START up to
  49    WHEEL_END is reused periodically, while the "lead in" is used to test
  50    for those primes and to jump onto the wheel.  For more information, see
  51    http://www.utm.edu/research/primes/glossary/WheelFactorization.html  */
  52
  53 #include "wheel-size.h"  /* For the definition of WHEEL_SIZE.  */
  54 static const unsigned int wheel_tab[] =
  55   {
  56 #include "wheel.h"
  57   };
  58
  59 #define WHEEL_START (wheel_tab + WHEEL_SIZE)
  60 #define WHEEL_END (wheel_tab + (sizeof wheel_tab / sizeof wheel_tab[0]))
  61
  62 /* The name this program was run with. */
  63 char *program_name;
  64
  65 void
  66 usage (int status)
  67 {
  68   if (status != 0)
  69     fprintf (stderr, _("Try `%s --help' for more information.\n"),
  70              program_name);
  71   else
  72     {
  73       printf (_("\
  74 Usage: %s [NUMBER]...\n\
  75   or:  %s OPTION\n\
  76 "),
  77               program_name, program_name);
  78       fputs (_("\
  79 Print the prime factors of each NUMBER.\n\
  80 \n\
  81 "), stdout);
  82       fputs (HELP_OPTION_DESCRIPTION, stdout);
  83       fputs (VERSION_OPTION_DESCRIPTION, stdout);
  84       fputs (_("\
  85 \n\
  86   Print the prime factors of all specified integer NUMBERs.  If no arguments\n\
  87   are specified on the command line, they are read from standard input.\n\
  88 "), stdout);
  89       printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
  90     }
  91   exit (status);
  92 }
  93
  94 /* FIXME: comment */
  95
  96 static int
  97 factor (uintmax_t n0, int max_n_factors, uintmax_t *factors)
  98 {
  99   register uintmax_t n = n0, d, q;
 100   int n_factors = 0;
 101   unsigned int const *w = wheel_tab;
 102
 103   if (n < 1)
 104     return n_factors;
 105
 106   /* The exit condition in the following loop is correct because
 107      any time it is tested one of these 3 conditions holds:
 108       (1) d divides n
 109       (2) n is prime
 110       (3) n is composite but has no factors less than d.
 111      If (1) or (2) obviously the right thing happens.
 112      If (3), then since n is composite it is >= d^2. */
 113
 114   d = 2;
 115   do
 116     {
 117       q = n / d;
 118       while (n == q * d)
 119         {
 120           assert (n_factors < max_n_factors);
 121           factors[n_factors++] = d;
 122           n = q;
 123           q = n / d;
 124         }
 125       d += *(w++);
 126       if (w == WHEEL_END)
 127         w = WHEEL_START;
 128     }
 129   while (d <= q);
 130
 131   if (n != 1 || n0 == 1)
 132     {
 133       assert (n_factors < max_n_factors);
 134       factors[n_factors++] = n;
 135     }
 136
 137   return n_factors;
 138 }
 139
 140 /* FIXME: comment */
 141
 142 static int
 143 print_factors (const char *s)
 144 {
 145   uintmax_t factors[MAX_N_FACTORS];
 146   uintmax_t n;
 147   int n_factors;
 148   int i;
 149   char buf[INT_BUFSIZE_BOUND (uintmax_t)];
 150   strtol_error err;
 151
 152   if ((err = xstrtoumax (s, NULL, 10, &n, "")) != LONGINT_OK)
 153     {
 154       if (err == LONGINT_OVERFLOW)
 155         error (0, 0, _("`%s' is too large"), s);
 156       else
 157         error (0, 0, _("`%s' is not a valid positive integer"), s);
 158       return 1;
 159     }
 160   n_factors = factor (n, MAX_N_FACTORS, factors);
 161   printf ("%s:", umaxtostr (n, buf));
 162   for (i = 0; i < n_factors; i++)
 163     printf (" %s", umaxtostr (factors[i], buf));
 164   putchar ('\n');
 165   return 0;
 166 }
 167
 168 static int
 169 do_stdin (void)
 170 {
 171   int fail = 0;
 172   token_buffer tokenbuffer;
 173
 174   init_tokenbuffer (&tokenbuffer);
 175
 176   for (;;)
 177     {
 178       long int token_length;
 179
 180       token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
 181                                 &tokenbuffer);
 182       if (token_length < 0)
 183         break;
 184       fail |= print_factors (tokenbuffer.buffer);
 185     }
 186   free (tokenbuffer.buffer);
 187
 188   return fail;
 189 }
 190
 191 int
 192 main (int argc, char **argv)
 193 {
 194   int fail;
 195
 196   initialize_main (&argc, &argv);
 197   program_name = argv[0];
 198   setlocale (LC_ALL, "");
 199   bindtextdomain (PACKAGE, LOCALEDIR);
 200   textdomain (PACKAGE);
 201
 202   atexit (close_stdout);
 203
 204   parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
 205                       usage, AUTHORS, NULL);
 206   /* The above handles --help and --version.
 207      Since there is no other invocation of getopt, handle `--' here.  */
 208   if (argc > 1 && STREQ (argv[1], "--"))
 209     {
 210       --argc;
 211       ++argv;
 212     }
 213
 214   fail = 0;
 215   if (argc == 1)
 216     fail = do_stdin ();
 217   else
 218     {
 219       int i;
 220       for (i = 1; i < argc; i++)
 221         fail |= print_factors (argv[i]);
 222     }
 223   if (fail)
 224     usage (EXIT_FAILURE);
 225
 226   exit (fail);
 227 }