1 /* factor -- print prime factors of n.
2 Copyright (C) 86, 1995-2005, 2007 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 3 of the License, or
7 (at your option) any later version.
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, see <http://www.gnu.org/licenses/>. */
17 /* Written by Paul Rubin <phr@ocf.berkeley.edu>.
18 Adapted for GNU, fixed to factor UINT_MAX by Jim Meyering. */
23 #include <sys/types.h>
31 #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 /* The maximum number of factors, including -1, for negative numbers. */
45 #define MAX_N_FACTORS (sizeof (uintmax_t) * CHAR_BIT)
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 */
53 #include "wheel-size.h" /* For the definition of WHEEL_SIZE. */
54 static const unsigned char wheel_tab
[] =
59 #define WHEEL_START (wheel_tab + WHEEL_SIZE)
60 #define WHEEL_END (wheel_tab + (sizeof wheel_tab / sizeof wheel_tab[0]))
62 /* The name this program was run with. */
68 if (status
!= EXIT_SUCCESS
)
69 fprintf (stderr
, _("Try `%s --help' for more information.\n"),
74 Usage: %s [NUMBER]...\n\
77 program_name
, program_name
);
79 Print the prime factors of each NUMBER.\n\
82 fputs (HELP_OPTION_DESCRIPTION
, stdout
);
83 fputs (VERSION_OPTION_DESCRIPTION
, stdout
);
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\
89 emit_bug_reporting_address ();
97 factor (uintmax_t n0
, size_t max_n_factors
, uintmax_t *factors
)
99 uintmax_t n
= n0
, d
, q
;
100 size_t n_factors
= 0;
101 unsigned char const *w
= wheel_tab
;
106 /* The exit condition in the following loop is correct because
107 any time it is tested one of these 3 conditions holds:
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. */
120 assert (n_factors
< max_n_factors
);
121 factors
[n_factors
++] = d
;
131 if (n
!= 1 || n0
== 1)
133 assert (n_factors
< max_n_factors
);
134 factors
[n_factors
++] = n
;
143 print_factors (const char *s
)
145 uintmax_t factors
[MAX_N_FACTORS
];
149 char buf
[INT_BUFSIZE_BOUND (uintmax_t)];
152 if ((err
= xstrtoumax (s
, NULL
, 10, &n
, "")) != LONGINT_OK
)
154 if (err
== LONGINT_OVERFLOW
)
155 error (0, 0, _("%s is too large"), quote (s
));
157 error (0, 0, _("%s is not a valid positive integer"), quote (s
));
160 n_factors
= factor (n
, MAX_N_FACTORS
, factors
);
161 printf ("%s:", umaxtostr (n
, buf
));
162 for (i
= 0; i
< n_factors
; i
++)
163 printf (" %s", umaxtostr (factors
[i
], buf
));
172 token_buffer tokenbuffer
;
174 init_tokenbuffer (&tokenbuffer
);
178 size_t token_length
= readtoken (stdin
, DELIM
, sizeof (DELIM
) - 1,
180 if (token_length
== (size_t) -1)
182 ok
&= print_factors (tokenbuffer
.buffer
);
184 free (tokenbuffer
.buffer
);
190 main (int argc
, char **argv
)
194 initialize_main (&argc
, &argv
);
195 program_name
= argv
[0];
196 setlocale (LC_ALL
, "");
197 bindtextdomain (PACKAGE
, LOCALEDIR
);
198 textdomain (PACKAGE
);
200 atexit (close_stdout
);
202 parse_long_options (argc
, argv
, PROGRAM_NAME
, PACKAGE_NAME
, VERSION
,
203 usage
, AUTHORS
, (char const *) NULL
);
204 if (getopt_long (argc
, argv
, "", NULL
, NULL
) != -1)
205 usage (EXIT_FAILURE
);
213 for (i
= optind
; i
< argc
; i
++)
214 if (! print_factors (argv
[i
]))
218 exit (ok
? EXIT_SUCCESS
: EXIT_FAILURE
);