src/factor.c

   1 /* factor -- print prime factors of n.
   2    Copyright (C) 86, 1995-2005 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 <getopt.h>
  23 #include <stdio.h>
  24 #include <sys/types.h>
  25
  26 #include <assert.h>
  27 #define NDEBUG 1
  28
  29 #include "system.h"
  30 #include "error.h"
  31 #include "inttostr.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 char 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 != EXIT_SUCCESS)
  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 size_t
  98 factor (uintmax_t n0, size_t max_n_factors, uintmax_t *factors)
  99 {
 100   uintmax_t n = n0, d, q;
 101   size_t n_factors = 0;
 102   unsigned char 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 bool
 144 print_factors (const char *s)
 145 {
 146   uintmax_t factors[MAX_N_FACTORS];
 147   uintmax_t n;
 148   size_t n_factors;
 149   size_t i;
 150   char buf[INT_BUFSIZE_BOUND (uintmax_t)];
 151   strtol_error err;
 152
 153   if ((err = xstrtoumax (s, NULL, 10, &n, "")) != LONGINT_OK)
 154     {
 155       if (err == LONGINT_OVERFLOW)
 156         error (0, 0, _("`%s' is too large"), s);
 157       else
 158         error (0, 0, _("`%s' is not a valid positive integer"), s);
 159       return false;
 160     }
 161   n_factors = factor (n, MAX_N_FACTORS, factors);
 162   printf ("%s:", umaxtostr (n, buf));
 163   for (i = 0; i < n_factors; i++)
 164     printf (" %s", umaxtostr (factors[i], buf));
 165   putchar ('\n');
 166   return true;
 167 }
 168
 169 static bool
 170 do_stdin (void)
 171 {
 172   bool ok = true;
 173   token_buffer tokenbuffer;
 174
 175   init_tokenbuffer (&tokenbuffer);
 176
 177   for (;;)
 178     {
 179       size_t token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
 180                                        &tokenbuffer);
 181       if (token_length == (size_t) -1)
 182         break;
 183       ok &= print_factors (tokenbuffer.buffer);
 184     }
 185   free (tokenbuffer.buffer);
 186
 187   return ok;
 188 }
 189
 190 int
 191 main (int argc, char **argv)
 192 {
 193   bool ok;
 194
 195   initialize_main (&argc, &argv);
 196   program_name = argv[0];
 197   setlocale (LC_ALL, "");
 198   bindtextdomain (PACKAGE, LOCALEDIR);
 199   textdomain (PACKAGE);
 200
 201   atexit (close_stdout);
 202
 203   parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
 204                       usage, AUTHORS, (char const *) NULL);
 205   if (getopt_long (argc, argv, "", NULL, NULL) != -1)
 206     usage (EXIT_FAILURE);
 207
 208   if (argc <= optind)
 209     ok = do_stdin ();
 210   else
 211     {
 212       int i;
 213       for (i = optind; i < argc; i++)
 214         if (! print_factors (argv[i]))
 215           usage (EXIT_FAILURE);
 216       ok = true;
 217     }
 218
 219   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 220 }