src/factor.c

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