src/factor.c

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