src/factor.c

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