factor.c revision 8856 
1/*
2 * Copyright (c) 1989, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Landon Curt Noll.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 *    must display the following acknowledgement:
18 *	This product includes software developed by the University of
19 *	California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 *    may be used to endorse or promote products derived from this software
22 *    without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 */
36
37#ifndef lint
38static char copyright[] =
39"@(#) Copyright (c) 1989, 1993\n\
40	The Regents of the University of California.  All rights reserved.\n";
41#endif /* not lint */
42
43#ifndef lint
44static char sccsid[] = "@(#)factor.c	8.3 (Berkeley) 3/30/94";
45#endif /* not lint */
46
47/*
48 * factor - factor a number into primes
49 *
50 * By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
51 *
52 *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
53 *
54 * usage:
55 *	factor [number] ...
56 *
57 * The form of the output is:
58 *
59 *	number: factor1 factor1 factor2 factor3 factor3 factor3 ...
60 *
61 * where factor1 < factor2 < factor3 < ...
62 *
63 * If no args are given, the list of numbers are read from stdin.
64 */
65
66#include <err.h>
67#include <ctype.h>
68#include <errno.h>
69#include <limits.h>
70#include <stdio.h>
71#include <stdlib.h>
72
73#include "primes.h"
74
75/*
76 * prime[i] is the (i-1)th prime.
77 *
78 * We are able to sieve 2^32-1 because this byte table yields all primes
79 * up to 65537 and 65537^2 > 2^32-1.
80 */
81extern ubig prime[];
82extern ubig *pr_limit;		/* largest prime in the prime array */
83
84void	pr_fact __P((ubig));	/* print factors of a value */
85void	usage __P((void));
86
87int
88main(argc, argv)
89	int argc;
90	char *argv[];
91{
92	ubig val;
93	int ch;
94	char *p, buf[100];		/* > max number of digits. */
95
96	while ((ch = getopt(argc, argv, "")) != EOF)
97		switch (ch) {
98		case '?':
99		default:
100			usage();
101		}
102	argc -= optind;
103	argv += optind;
104
105	/* No args supplied, read numbers from stdin. */
106	if (argc == 0)
107		for (;;) {
108			if (fgets(buf, sizeof(buf), stdin) == NULL) {
109				if (ferror(stdin))
110					err(1, "stdin");
111				exit (0);
112			}
113			for (p = buf; isblank(*p); ++p);
114			if (*p == '\n' || *p == '\0')
115				continue;
116			if (*p == '-')
117				errx(1, "negative numbers aren't permitted.");
118			errno = 0;
119			val = strtoul(buf, &p, 10);
120			if (errno)
121				err(1, "%s", buf);
122			if (*p != '\n')
123				errx(1, "%s: illegal numeric format.", buf);
124			pr_fact(val);
125		}
126	/* Factor the arguments. */
127	else
128		for (; *argv != NULL; ++argv) {
129			if (argv[0][0] == '-')
130				errx(1, "negative numbers aren't permitted.");
131			errno = 0;
132			val = strtoul(argv[0], &p, 10);
133			if (errno)
134				err(1, "%s", argv[0]);
135			if (*p != '\0')
136				errx(1, "%s: illegal numeric format.", argv[0]);
137			pr_fact(val);
138		}
139	exit(0);
140}
141
142/*
143 * pr_fact - print the factors of a number
144 *
145 * If the number is 0 or 1, then print the number and return.
146 * If the number is < 0, print -1, negate the number and continue
147 * processing.
148 *
149 * Print the factors of the number, from the lowest to the highest.
150 * A factor will be printed numtiple times if it divides the value
151 * multiple times.
152 *
153 * Factors are printed with leading tabs.
154 */
155void
156pr_fact(val)
157	ubig val;		/* Factor this value. */
158{
159	ubig *fact;		/* The factor found. */
160
161	/* Firewall - catch 0 and 1. */
162	if (val == 0)		/* Historical practice; 0 just exits. */
163		exit(0);
164	if (val == 1) {
165		(void)printf("1: 1\n");
166		return;
167	}
168
169	/* Factor value. */
170	(void)printf("%lu:", val);
171	for (fact = &prime[0]; val > 1; ++fact) {
172		/* Look for the smallest factor. */
173		do {
174			if (val % (long)*fact == 0)
175				break;
176		} while (++fact <= pr_limit);
177
178		/* Watch for primes larger than the table. */
179		if (fact > pr_limit) {
180			(void)printf(" %lu", val);
181			break;
182		}
183
184		/* Divide factor out until none are left. */
185		do {
186			(void)printf(" %lu", *fact);
187			val /= (long)*fact;
188		} while ((val % (long)*fact) == 0);
189
190		/* Let the user know we're doing something. */
191		(void)fflush(stdout);
192	}
193	(void)putchar('\n');
194}
195
196void
197usage()
198{
199	(void)fprintf(stderr, "usage: factor [value ...]\n");
200	exit (0);
201}
202