1 /* factor -- print factors of n.
2 Copyright (C) 86, 95, 96, 1997, 1998, 1999, 2000 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>
32 #include "long-options.h"
33 #include "readtokens.h"
36 /* The official name of this program (e.g., no `g' prefix). */
37 #define PROGRAM_NAME "factor"
39 #define AUTHORS "Paul Rubin"
41 /* Token delimiters when reading from a file. */
44 /* FIXME: if this program is ever modified to factor integers larger
45 than 2^128, this constant (and the algorithm :-) will have to change. */
46 #define MAX_N_FACTORS 128
48 /* The name this program was run with. */
55 fprintf (stderr, _("Try `%s --help' for more information.\n"),
60 Usage: %s [NUMBER]...\n\
63 program_name, program_name);
65 Print factors of each NUMBER; read standard input with no arguments.\n\
67 --help display this help and exit\n\
68 --version output version information and exit\n\
70 Print the prime factors of all specified integer NUMBERs. If no arguments\n\
71 are specified on the command line, they are read from standard input.\n\
73 puts (_("\nReport bugs to <bug-sh-utils@gnu.org>."));
81 factor (uintmax_t n0, int max_n_factors, uintmax_t *factors)
83 register uintmax_t n = n0, d, q;
91 assert (n_factors < max_n_factors);
92 factors[n_factors++] = 2;
96 /* The exit condition in the following loop is correct because
97 any time it is tested one of these 3 conditions holds:
100 (3) n is composite but has no factors less than d.
101 If (1) or (2) obviously the right thing happens.
102 If (3), then since n is composite it is >= d^2. */
110 assert (n_factors < max_n_factors);
111 factors[n_factors++] = d;
119 if (n != 1 || n0 == 1)
121 assert (n_factors < max_n_factors);
122 factors[n_factors++] = n;
131 print_factors (const char *s)
133 uintmax_t factors[MAX_N_FACTORS];
137 char buf[LONGEST_HUMAN_READABLE + 1];
139 if (xstrtoumax (s, NULL, 10, &n, "") != LONGINT_OK)
141 error (0, 0, _("`%s' is not a valid positive integer"), s);
144 n_factors = factor (n, MAX_N_FACTORS, factors);
145 printf ("%s:", human_readable (n, buf, 1, 1));
146 for (i = 0; i < n_factors; i++)
147 printf (" %s", human_readable (factors[i], buf, 1, 1));
156 token_buffer tokenbuffer;
158 init_tokenbuffer (&tokenbuffer);
162 long int token_length;
164 token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
166 if (token_length < 0)
168 fail |= print_factors (tokenbuffer.buffer);
170 free (tokenbuffer.buffer);
176 main (int argc, char **argv)
180 program_name = argv[0];
181 setlocale (LC_ALL, "");
182 bindtextdomain (PACKAGE, LOCALEDIR);
183 textdomain (PACKAGE);
185 parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
187 /* The above handles --help and --version.
188 Since there is no other invocation of getopt, handle `--' here. */
189 if (argc > 1 && STREQ (argv[1], "--"))
201 for (i = 1; i < argc; i++)
202 fail |= print_factors (argv[i]);