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