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
  20 #include <config.h>
  21 #include <stdio.h>
  22 #include <sys/types.h>
  23 #include <assert.h>
  24
  25 #define NDEBUG 1
  26
  27 #include "system.h"
  28 #include "version.h"
  29 #include "long-options.h"
  30 #include "error.h"
  31 #include "readtokens.h"
  32
  33 /* Token delimiters when reading from a file.  */
  34 #define DELIM "\n\t "
  35
  36 /* FIXME: if this program is ever modified to factor integers larger
  37    than 2^128, this (and the algorithm :-) will have to change.  */
  38 #define MAX_N_FACTORS 128
  39
  40 /* The name this program was run with. */
  41 char *program_name;
  42
  43 static void
  44 usage (status)
  45      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 \n\
  59   --help      display this help and exit\n\
  60   --version   output version information and exit\n\
  61 ");
  62     }
  63   exit (status);
  64 }
  65
  66 static int
  67 factor (n0, max_n_factors, factors)
  68      unsigned long n0;
  69      int max_n_factors;
  70      unsigned long *factors;
  71 {
  72   register unsigned long n = n0, d;
  73   int n_factors = 0;
  74
  75   if (n < 1)
  76     return n_factors;
  77
  78   while (n % 2 == 0)
  79     {
  80       assert (n_factors < max_n_factors);
  81       factors[n_factors++] = 2;
  82       n /= 2;
  83     }
  84
  85   /* The exit condition in the following loop is correct because
  86      any time it is tested one of these 3 conditions holds:
  87       (1) d divides n
  88       (2) n is prime
  89       (3) n is composite but has no factors less than d.
  90      If (1) or (2) obviously the right thing happens.
  91      If (3), then since n is composite it is >= d^2. */
  92   for (d = 3; d * d <= n; d += 2)
  93     {
  94       while (n % d == 0)
  95         {
  96           assert (n_factors < max_n_factors);
  97           factors[n_factors++] = d;
  98           n /= d;
  99         }
 100     }
 101   if (n != 1 || n0 == 1)
 102     {
 103       assert (n_factors < max_n_factors);
 104       factors[n_factors++] = n;
 105     }
 106
 107   return n_factors;
 108 }
 109
 110 static void
 111 print_factors (n)
 112      unsigned long int n;
 113 {
 114   unsigned long int factors[MAX_N_FACTORS];
 115   int n_factors;
 116   int i;
 117
 118   n_factors = factor (n, MAX_N_FACTORS, factors);
 119   for (i = 0; i < n_factors; i++)
 120     printf ("     %lu\n", factors[i]);
 121   putchar ('\n');
 122 }
 123
 124 static void
 125 do_stdin ()
 126 {
 127   token_buffer tokenbuffer;
 128
 129   init_tokenbuffer (&tokenbuffer);
 130
 131   for (;;)
 132     {
 133       long int token_length;
 134
 135       token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
 136                                 &tokenbuffer);
 137       if (token_length < 0)
 138         break;
 139       /* FIXME: Use xstrtoul, not atoi.  */
 140       print_factors ((unsigned long) atoi (tokenbuffer.buffer));
 141     }
 142   free (tokenbuffer.buffer);
 143 }
 144
 145 void
 146 main (argc, argv)
 147      int argc;
 148      char **argv;
 149 {
 150   program_name = argv[0];
 151
 152   parse_long_options (argc, argv, "factor", version_string, usage);
 153
 154   if (argc > 2)
 155     {
 156       error (0, 0, "too many arguments");
 157       usage (1);
 158     }
 159
 160   if (argc == 1)
 161     do_stdin ();
 162   else if (argc == 2)
 163     {
 164       print_factors ((unsigned long) atoi (argv[1]));
 165     }
 166   else
 167     {
 168       fprintf (stderr, "Usage: %s [number]\n", argv[0]);
 169       exit (1);
 170     }
 171   exit (0);
 172 }