1 /* factor -- print factors of n. lose if n > 2^32.
2 Copyright (C) 86, 1995, 96 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. */
24 #include <sys/types.h>
31 #endif /* HAVE_LIMITS_H */
34 # define UINT_MAX ((unsigned int) ~(unsigned int) 0)
38 # define INT_MAX ((int) (UINT_MAX >> 1))
42 #include "long-options.h"
45 #include "readtokens.h"
47 /* Token delimiters when reading from a file. */
50 /* FIXME: if this program is ever modified to factor integers larger
51 than 2^128, this constant (and the algorithm :-) will have to change. */
52 #define MAX_N_FACTORS 128
54 /* The name this program was run with. */
61 fprintf (stderr, _("Try `%s --help' for more information.\n"),
66 Usage: %s [NUMBER]...\n\
69 program_name, program_name);
71 Print factors of each NUMBER; read standard input with no arguments.\n\
73 --help display this help and exit\n\
74 --version output version information and exit\n\
76 Print the prime factors of all specified integer NUMBERs. If no arguments\n\
77 are specified on the command line, they are read from standard input.\n\
86 factor (long unsigned int n0, int max_n_factors, long unsigned int *factors)
88 register unsigned long n = n0, d;
97 assert (n_factors < max_n_factors);
98 factors[n_factors++] = 2;
102 /* The exit condition in the following loop is correct because
103 any time it is tested one of these 3 conditions holds:
106 (3) n is composite but has no factors less than d.
107 If (1) or (2) obviously the right thing happens.
108 If (3), then since n is composite it is >= d^2. */
109 sqrt_n = (unsigned int) sqrt ((double) n);
110 for (d = 3; d <= sqrt_n; d += 2)
114 assert (n_factors < max_n_factors);
115 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 unsigned long int factors[MAX_N_FACTORS];
138 if (xstrtoul (s, NULL, 10, &n, NULL) != LONGINT_OK)
140 error (0, 0, _("`%s' is not a valid positive integer"), s);
143 n_factors = factor (n, MAX_N_FACTORS, factors);
145 for (i = 0; i < n_factors; i++)
146 printf (" %lu", factors[i]);
155 token_buffer tokenbuffer;
157 init_tokenbuffer (&tokenbuffer);
161 long int token_length;
163 token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
165 if (token_length < 0)
167 fail |= print_factors (tokenbuffer.buffer);
169 free (tokenbuffer.buffer);
175 main (int argc, char **argv)
179 program_name = argv[0];
180 setlocale (LC_ALL, "");
181 bindtextdomain (PACKAGE, LOCALEDIR);
182 textdomain (PACKAGE);
184 parse_long_options (argc, argv, "factor", PACKAGE_VERSION, usage);
192 for (i = 1; i < argc; i++)
193 fail |= print_factors (argv[i]);