factor.c revision 28979 
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.4 (Berkeley) 5/4/95";
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#include <unistd.h>
73
74#include "primes.h"
75
76/*
77 * prime[i] is the (i-1)th prime.
78 *
79 * We are able to sieve 2^32-1 because this byte table yields all primes
80 * up to 65537 and 65537^2 > 2^32-1.
81 */
82extern ubig prime[];
83extern ubig *pr_limit;		/* largest prime in the prime array */
84
85void	pr_fact __P((ubig));	/* print factors of a value */
86void	usage __P((void));
87
88int
89main(argc, argv)
90	int argc;
91	char *argv[];
92{
93	ubig val;
94	int ch;
95	char *p, buf[100];		/* > max number of digits. */
96
97	/* revoke privs */
98	setegid(getgid());
99	setgid(getgid());
100
101	while ((ch = getopt(argc, argv, "")) != EOF)
102		switch (ch) {
103		case '?':
104		default:
105			usage();
106		}
107	argc -= optind;
108	argv += optind;
109
110	/* No args supplied, read numbers from stdin. */
111	if (argc == 0)
112		for (;;) {
113			if (fgets(buf, sizeof(buf), stdin) == NULL) {
114				if (ferror(stdin))
115					err(1, "stdin");
116				exit (0);
117			}
118			for (p = buf; isblank(*p); ++p);
119			if (*p == '\n' || *p == '\0')
120				continue;
121			if (*p == '-')
122				errx(1, "negative numbers aren't permitted.");
123			errno = 0;
124			val = strtoul(buf, &p, 10);
125			if (errno)
126				err(1, "%s", buf);
127			if (*p != '\n')
128				errx(1, "%s: illegal numeric format.", buf);
129			pr_fact(val);
130		}
131	/* Factor the arguments. */
132	else
133		for (; *argv != NULL; ++argv) {
134			if (argv[0][0] == '-')
135				errx(1, "negative numbers aren't permitted.");
136			errno = 0;
137			val = strtoul(argv[0], &p, 10);
138			if (errno)
139				err(1, "%s", argv[0]);
140			if (*p != '\0')
141				errx(1, "%s: illegal numeric format.", argv[0]);
142			pr_fact(val);
143		}
144	exit(0);
145}
146
147/*
148 * pr_fact - print the factors of a number
149 *
150 * If the number is 0 or 1, then print the number and return.
151 * If the number is < 0, print -1, negate the number and continue
152 * processing.
153 *
154 * Print the factors of the number, from the lowest to the highest.
155 * A factor will be printed numtiple times if it divides the value
156 * multiple times.
157 *
158 * Factors are printed with leading tabs.
159 */
160void
161pr_fact(val)
162	ubig val;		/* Factor this value. */
163{
164	ubig *fact;		/* The factor found. */
165
166	/* Firewall - catch 0 and 1. */
167	if (val == 0)		/* Historical practice; 0 just exits. */
168		exit(0);
169	if (val == 1) {
170		(void)printf("1: 1\n");
171		return;
172	}
173
174	/* Factor value. */
175	(void)printf("%lu:", val);
176	for (fact = &prime[0]; val > 1; ++fact) {
177		/* Look for the smallest factor. */
178		do {
179			if (val % (long)*fact == 0)
180				break;
181		} while (++fact <= pr_limit);
182
183		/* Watch for primes larger than the table. */
184		if (fact > pr_limit) {
185			(void)printf(" %lu", val);
186			break;
187		}
188
189		/* Divide factor out until none are left. */
190		do {
191			(void)printf(" %lu", *fact);
192			val /= (long)*fact;
193		} while ((val % (long)*fact) == 0);
194
195		/* Let the user know we're doing something. */
196		(void)fflush(stdout);
197	}
198	(void)putchar('\n');
199}
200
201void
202usage()
203{
204	(void)fprintf(stderr, "usage: factor [value ...]\n");
205	exit (0);
206}
207