1 /* factor -- print prime factors of n.
2 Copyright (C) 86, 1995-2001 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 trial divisor increment wheel. Use it to skip over divisors that
49 are composites of 2, 3, 5, 7, or 11. The part from WHEEL_START up to
50 WHEEL_END is reused periodically, while the "lead in" is used to test
51 for those primes and to jump onto the wheel. For more information, see
52 http://www.utm.edu/research/primes/glossary/WheelFactorization.html */
54 #include "wheel-size.h" /* For the definition of WHEEL_SIZE. */
55 static const unsigned int wheel_tab[] =
60 #define WHEEL_START (wheel_tab + WHEEL_SIZE)
61 #define WHEEL_END (wheel_tab + (sizeof wheel_tab / sizeof wheel_tab[0]))
63 /* The name this program was run with. */
70 fprintf (stderr, _("Try `%s --help' for more information.\n"),
75 Usage: %s [NUMBER]...\n\
78 program_name, program_name);
80 Print the prime factors of each NUMBER.\n\
83 fputs (HELP_OPTION_DESCRIPTION, stdout);
84 fputs (VERSION_OPTION_DESCRIPTION, stdout);
87 Print the prime factors of all specified integer NUMBERs. If no arguments\n\
88 are specified on the command line, they are read from standard input.\n\
90 printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
98 factor (uintmax_t n0, int max_n_factors, uintmax_t *factors)
100 register uintmax_t n = n0, d, q;
102 unsigned int const *w = wheel_tab;
107 /* The exit condition in the following loop is correct because
108 any time it is tested one of these 3 conditions holds:
111 (3) n is composite but has no factors less than d.
112 If (1) or (2) obviously the right thing happens.
113 If (3), then since n is composite it is >= d^2. */
121 assert (n_factors < max_n_factors);
122 factors[n_factors++] = d;
132 if (n != 1 || n0 == 1)
134 assert (n_factors < max_n_factors);
135 factors[n_factors++] = n;
144 print_factors (const char *s)
146 uintmax_t factors[MAX_N_FACTORS];
150 char buf[LONGEST_HUMAN_READABLE + 1];
152 if (xstrtoumax (s, NULL, 10, &n, "") != LONGINT_OK)
154 error (0, 0, _("`%s' is not a valid positive integer"), s);
157 n_factors = factor (n, MAX_N_FACTORS, factors);
158 printf ("%s:", human_readable (n, buf, 1, 1));
159 for (i = 0; i < n_factors; i++)
160 printf (" %s", human_readable (factors[i], buf, 1, 1));
169 token_buffer tokenbuffer;
171 init_tokenbuffer (&tokenbuffer);
175 long int token_length;
177 token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
179 if (token_length < 0)
181 fail |= print_factors (tokenbuffer.buffer);
183 free (tokenbuffer.buffer);
189 main (int argc, char **argv)
193 program_name = argv[0];
194 setlocale (LC_ALL, "");
195 bindtextdomain (PACKAGE, LOCALEDIR);
196 textdomain (PACKAGE);
198 atexit (close_stdout);
200 parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
202 /* The above handles --help and --version.
203 Since there is no other invocation of getopt, handle `--' here. */
204 if (argc > 1 && STREQ (argv[1], "--"))
216 for (i = 1; i < argc; i++)
217 fail |= print_factors (argv[i]);