src/factor.c

   1 /* factor -- print prime factors of n.
   2    Copyright (C) 86, 1995-2005, 2007 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 3 of the License, or
   7    (at your option) 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, see <http://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Paul Rubin <phr@ocf.berkeley.edu>.
  18    Adapted for GNU, fixed to factor UINT_MAX by Jim Meyering.  */
  19
  20 #include <config.h>
  21 #include <getopt.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 "quote.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 /* The maximum number of factors, including -1, for negative numbers.  */
  45 #define MAX_N_FACTORS (sizeof (uintmax_t) * CHAR_BIT)
  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 char 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 != EXIT_SUCCESS)
  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       emit_bug_reporting_address ();
  90     }
  91   exit (status);
  92 }
  93
  94 /* FIXME: comment */
  95
  96 static size_t
  97 factor (uintmax_t n0, size_t max_n_factors, uintmax_t *factors)
  98 {
  99   uintmax_t n = n0, d, q;
 100   size_t n_factors = 0;
 101   unsigned char 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 bool
 143 print_factors (const char *s)
 144 {
 145   uintmax_t factors[MAX_N_FACTORS];
 146   uintmax_t n;
 147   size_t n_factors;
 148   size_t 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"), quote (s));
 156       else
 157         error (0, 0, _("%s is not a valid positive integer"), quote (s));
 158       return false;
 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 true;
 166 }
 167
 168 static bool
 169 do_stdin (void)
 170 {
 171   bool ok = true;
 172   token_buffer tokenbuffer;
 173
 174   init_tokenbuffer (&tokenbuffer);
 175
 176   for (;;)
 177     {
 178       size_t token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
 179                                        &tokenbuffer);
 180       if (token_length == (size_t) -1)
 181         break;
 182       ok &= print_factors (tokenbuffer.buffer);
 183     }
 184   free (tokenbuffer.buffer);
 185
 186   return ok;
 187 }
 188
 189 int
 190 main (int argc, char **argv)
 191 {
 192   bool ok;
 193
 194   initialize_main (&argc, &argv);
 195   program_name = argv[0];
 196   setlocale (LC_ALL, "");
 197   bindtextdomain (PACKAGE, LOCALEDIR);
 198   textdomain (PACKAGE);
 199
 200   atexit (close_stdout);
 201
 202   parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE_NAME, VERSION,
 203                       usage, AUTHORS, (char const *) NULL);
 204   if (getopt_long (argc, argv, "", NULL, NULL) != -1)
 205     usage (EXIT_FAILURE);
 206
 207   if (argc <= optind)
 208     ok = do_stdin ();
 209   else
 210     {
 211       int i;
 212       ok = true;
 213       for (i = optind; i < argc; i++)
 214         if (! print_factors (argv[i]))
 215           ok = false;
 216     }
 217
 218   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 219 }