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