Line data Source code
1 : /* factor -- print prime factors of n.
2 : Copyright (C) 86, 1995-2005, 2007 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 3 of the License, or
7 : (at your option) 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, see <http://www.gnu.org/licenses/>. */
16 :
17 : /* Written by Paul Rubin <phr@ocf.berkeley.edu>.
18 : Adapted for GNU, fixed to factor UINT_MAX by Jim Meyering. */
19 :
20 : #include <config.h>
21 : #include <getopt.h>
22 : #include <stdio.h>
23 : #include <sys/types.h>
24 :
25 : #include <assert.h>
26 : #define NDEBUG 1
27 :
28 : #include "system.h"
29 : #include "error.h"
30 : #include "inttostr.h"
31 : #include "long-options.h"
32 : #include "quote.h"
33 : #include "readtokens.h"
34 : #include "xstrtol.h"
35 :
36 : /* The official name of this program (e.g., no `g' prefix). */
37 : #define PROGRAM_NAME "factor"
38 :
39 : #define AUTHORS "Paul Rubin"
40 :
41 : /* Token delimiters when reading from a file. */
42 : #define DELIM "\n\t "
43 :
44 : /* The maximum number of factors, including -1, for negative numbers. */
45 : #define MAX_N_FACTORS (sizeof (uintmax_t) * CHAR_BIT)
46 :
47 : /* The trial divisor increment wheel. Use it to skip over divisors that
48 : are composites of 2, 3, 5, 7, or 11. The part from WHEEL_START up to
49 : WHEEL_END is reused periodically, while the "lead in" is used to test
50 : for those primes and to jump onto the wheel. For more information, see
51 : http://www.utm.edu/research/primes/glossary/WheelFactorization.html */
52 :
53 : #include "wheel-size.h" /* For the definition of WHEEL_SIZE. */
54 : static const unsigned char wheel_tab[] =
55 : {
56 : #include "wheel.h"
57 : };
58 :
59 : #define WHEEL_START (wheel_tab + WHEEL_SIZE)
60 : #define WHEEL_END (wheel_tab + (sizeof wheel_tab / sizeof wheel_tab[0]))
61 :
62 : /* The name this program was run with. */
63 : char *program_name;
64 :
65 : void
66 6 : usage (int status)
67 : {
68 6 : if (status != EXIT_SUCCESS)
69 5 : fprintf (stderr, _("Try `%s --help' for more information.\n"),
70 : program_name);
71 : else
72 : {
73 1 : printf (_("\
74 : Usage: %s [NUMBER]...\n\
75 : or: %s OPTION\n\
76 : "),
77 : program_name, program_name);
78 1 : fputs (_("\
79 : Print the prime factors of each NUMBER.\n\
80 : \n\
81 : "), stdout);
82 1 : fputs (HELP_OPTION_DESCRIPTION, stdout);
83 1 : fputs (VERSION_OPTION_DESCRIPTION, stdout);
84 1 : fputs (_("\
85 : \n\
86 : Print the prime factors of all specified integer NUMBERs. If no arguments\n\
87 : are specified on the command line, they are read from standard input.\n\
88 : "), stdout);
89 1 : emit_bug_reporting_address ();
90 : }
91 6 : exit (status);
92 : }
93 :
94 : /* FIXME: comment */
95 :
96 : static size_t
97 16 : factor (uintmax_t n0, size_t max_n_factors, uintmax_t *factors)
98 : {
99 16 : uintmax_t n = n0, d, q;
100 16 : size_t n_factors = 0;
101 16 : unsigned char const *w = wheel_tab;
102 :
103 16 : if (n <= 1)
104 11 : return n_factors;
105 :
106 : /* The exit condition in the following loop is correct because
107 : any time it is tested one of these 3 conditions holds:
108 : (1) d divides n
109 : (2) n is prime
110 : (3) n is composite but has no factors less than d.
111 : If (1) or (2) obviously the right thing happens.
112 : If (3), then since n is composite it is >= d^2. */
113 :
114 5 : d = 2;
115 : do
116 : {
117 514 : q = n / d;
118 1082 : while (n == q * d)
119 : {
120 54 : assert (n_factors < max_n_factors);
121 54 : factors[n_factors++] = d;
122 54 : n = q;
123 54 : q = n / d;
124 : }
125 514 : d += *(w++);
126 514 : if (w == WHEEL_END)
127 1 : w = WHEEL_START;
128 : }
129 514 : while (d <= q);
130 :
131 5 : if (n != 1 || n0 == 1)
132 : {
133 3 : assert (n_factors < max_n_factors);
134 3 : factors[n_factors++] = n;
135 : }
136 :
137 5 : return n_factors;
138 : }
139 :
140 : /* FIXME: comment */
141 :
142 : static bool
143 82 : print_factors (const char *s)
144 : {
145 : uintmax_t factors[MAX_N_FACTORS];
146 : uintmax_t n;
147 : size_t n_factors;
148 : size_t i;
149 : char buf[INT_BUFSIZE_BOUND (uintmax_t)];
150 : strtol_error err;
151 :
152 82 : if ((err = xstrtoumax (s, NULL, 10, &n, "")) != LONGINT_OK)
153 : {
154 66 : if (err == LONGINT_OVERFLOW)
155 0 : error (0, 0, _("%s is too large"), quote (s));
156 : else
157 66 : error (0, 0, _("%s is not a valid positive integer"), quote (s));
158 66 : return false;
159 : }
160 16 : n_factors = factor (n, MAX_N_FACTORS, factors);
161 16 : printf ("%s:", umaxtostr (n, buf));
162 73 : for (i = 0; i < n_factors; i++)
163 57 : printf (" %s", umaxtostr (factors[i], buf));
164 16 : putchar ('\n');
165 16 : return true;
166 : }
167 :
168 : static bool
169 9 : do_stdin (void)
170 : {
171 9 : bool ok = true;
172 : token_buffer tokenbuffer;
173 :
174 9 : init_tokenbuffer (&tokenbuffer);
175 :
176 : for (;;)
177 15 : {
178 24 : size_t token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
179 : &tokenbuffer);
180 24 : if (token_length == (size_t) -1)
181 9 : break;
182 15 : ok &= print_factors (tokenbuffer.buffer);
183 : }
184 9 : free (tokenbuffer.buffer);
185 :
186 9 : return ok;
187 : }
188 :
189 : int
190 49 : main (int argc, char **argv)
191 : {
192 : bool ok;
193 :
194 : initialize_main (&argc, &argv);
195 49 : program_name = argv[0];
196 49 : setlocale (LC_ALL, "");
197 : bindtextdomain (PACKAGE, LOCALEDIR);
198 : textdomain (PACKAGE);
199 :
200 49 : atexit (close_stdout);
201 :
202 49 : parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE_NAME, VERSION,
203 : usage, AUTHORS, (char const *) NULL);
204 47 : if (getopt_long (argc, argv, "", NULL, NULL) != -1)
205 5 : usage (EXIT_FAILURE);
206 :
207 42 : if (argc <= optind)
208 9 : ok = do_stdin ();
209 : else
210 : {
211 : int i;
212 33 : ok = true;
213 100 : for (i = optind; i < argc; i++)
214 67 : if (! print_factors (argv[i]))
215 51 : ok = false;
216 : }
217 :
218 42 : exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
219 : }
|