src/factor.c

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