1 /* factor -- print factors of n. lose if n > 2^32.
2 Copyright (C) 86, 95, 96, 1997 Free Software Foundation, Inc.
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)
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.
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. */
18 /* Written by Paul Rubin <phr@ocf.berkeley.edu>.
19 Adapted for GNU, fixed to factor UINT_MAX by Jim Meyering. */
23 #include <sys/types.h>
30 #endif /* HAVE_LIMITS_H */
33 # define UINT_MAX ((unsigned int) ~(unsigned int) 0)
37 # define INT_MAX ((int) (UINT_MAX >> 1))
41 #include "long-options.h"
44 #include "readtokens.h"
46 /* Token delimiters when reading from a file. */
49 /* FIXME: if this program is ever modified to factor integers larger
50 than 2^128, this constant (and the algorithm :-) will have to change. */
51 #define MAX_N_FACTORS 128
53 /* The name this program was run with. */
60 fprintf (stderr, _("Try `%s --help' for more information.\n"),
65 Usage: %s [NUMBER]...\n\
68 program_name, program_name);
70 Print factors of each NUMBER; read standard input with no arguments.\n\
72 --help display this help and exit\n\
73 --version output version information and exit\n\
75 Print the prime factors of all specified integer NUMBERs. If no arguments\n\
76 are specified on the command line, they are read from standard input.\n\
78 puts (_("\nReport bugs to <sh-utils-bugs@gnu.ai.mit.edu>."));
86 factor (long unsigned int n0, int max_n_factors, long unsigned int *factors)
88 register unsigned long n = n0, d, q;
96 assert (n_factors < max_n_factors);
97 factors[n_factors++] = 2;
101 /* The exit condition in the following loop is correct because
102 any time it is tested one of these 3 conditions holds:
105 (3) n is composite but has no factors less than d.
106 If (1) or (2) obviously the right thing happens.
107 If (3), then since n is composite it is >= d^2. */
115 assert (n_factors < max_n_factors);
116 factors[n_factors++] = d;
124 if (n != 1 || n0 == 1)
126 assert (n_factors < max_n_factors);
127 factors[n_factors++] = n;
136 print_factors (const char *s)
138 unsigned long int factors[MAX_N_FACTORS];
143 if (xstrtoul (s, NULL, 10, &n, "") != LONGINT_OK)
145 error (0, 0, _("`%s' is not a valid positive integer"), s);
148 n_factors = factor (n, MAX_N_FACTORS, factors);
150 for (i = 0; i < n_factors; i++)
151 printf (" %lu", factors[i]);
160 token_buffer tokenbuffer;
162 init_tokenbuffer (&tokenbuffer);
166 long int token_length;
168 token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
170 if (token_length < 0)
172 fail |= print_factors (tokenbuffer.buffer);
174 free (tokenbuffer.buffer);
180 main (int argc, char **argv)
184 program_name = argv[0];
185 setlocale (LC_ALL, "");
186 bindtextdomain (PACKAGE, LOCALEDIR);
187 textdomain (PACKAGE);
189 parse_long_options (argc, argv, "factor", GNU_PACKAGE, VERSION, usage);
197 for (i = 1; i < argc; i++)
198 fail |= print_factors (argv[i]);