src/factor.c

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