src/factor.c

   1 /* factor -- print factors of n.  lose if n > 2^32.
   2    Copyright (C) 86, 1995, 96 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     }
  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;
  89   int n_factors = 0;
  90   unsigned int sqrt_n;
  91
  92   if (n < 1)
  93     return n_factors;
  94
  95   while (n % 2 == 0)
  96     {
  97       assert (n_factors < max_n_factors);
  98       factors[n_factors++] = 2;
  99       n /= 2;
 100     }
 101
 102   /* The exit condition in the following loop is correct because
 103      any time it is tested one of these 3 conditions holds:
 104       (1) d divides n
 105       (2) n is prime
 106       (3) n is composite but has no factors less than d.
 107      If (1) or (2) obviously the right thing happens.
 108      If (3), then since n is composite it is >= d^2. */
 109   sqrt_n = (unsigned int) sqrt ((double) n);
 110   for (d = 3; d <= sqrt_n; d += 2)
 111     {
 112       while (n % d == 0)
 113         {
 114           assert (n_factors < max_n_factors);
 115           factors[n_factors++] = d;
 116           n /= d;
 117         }
 118     }
 119   if (n != 1 || n0 == 1)
 120     {
 121       assert (n_factors < max_n_factors);
 122       factors[n_factors++] = n;
 123     }
 124
 125   return n_factors;
 126 }
 127
 128 /* FIXME: comment */
 129
 130 static int
 131 print_factors (const char *s)
 132 {
 133   unsigned long int factors[MAX_N_FACTORS];
 134   unsigned long n;
 135   int n_factors;
 136   int i;
 137
 138   if (xstrtoul (s, NULL, 10, &n, NULL) != LONGINT_OK)
 139     {
 140       error (0, 0, _("`%s' is not a valid positive integer"), s);
 141       return 1;
 142     }
 143   n_factors = factor (n, MAX_N_FACTORS, factors);
 144   printf ("%lu:", n);
 145   for (i = 0; i < n_factors; i++)
 146     printf (" %lu", factors[i]);
 147   putchar ('\n');
 148   return 0;
 149 }
 150
 151 static int
 152 do_stdin (void)
 153 {
 154   int fail = 0;
 155   token_buffer tokenbuffer;
 156
 157   init_tokenbuffer (&tokenbuffer);
 158
 159   for (;;)
 160     {
 161       long int token_length;
 162
 163       token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
 164                                 &tokenbuffer);
 165       if (token_length < 0)
 166         break;
 167       fail |= print_factors (tokenbuffer.buffer);
 168     }
 169   free (tokenbuffer.buffer);
 170
 171   return fail;
 172 }
 173
 174 int
 175 main (int argc, char **argv)
 176 {
 177   int fail;
 178
 179   program_name = argv[0];
 180   setlocale (LC_ALL, "");
 181   bindtextdomain (PACKAGE, LOCALEDIR);
 182   textdomain (PACKAGE);
 183
 184   parse_long_options (argc, argv, "factor", PACKAGE_VERSION, usage);
 185
 186   fail = 0;
 187   if (argc == 1)
 188     fail = do_stdin ();
 189   else
 190     {
 191       int i;
 192       for (i = 1; i < argc; i++)
 193         fail |= print_factors (argv[i]);
 194     }
 195   if (fail)
 196     usage (1);
 197
 198   exit (fail);
 199 }