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 * %sccs.include.redist.c%
9 */
10
11 #ifndef lint
12 static char copyright[] =
13 "@(#) Copyright (c) 1989, 1993\n\
14 The Regents of the University of California. All rights reserved.\n";
15 #endif /* not lint */
16
17 #ifndef lint
18 static char sccsid[] = "@(#)factor.c 8.4 (Berkeley) 05/04/95";
19 #endif /* not lint */
20
21 /*
22 * factor - factor a number into primes
23 *
24 * By: Landon Curt Noll chongo@toad.com, ...!{sun,tolsoft}!hoptoad!chongo
25 *
26 * chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
27 *
28 * usage:
29 * factor [number] ...
30 *
31 * The form of the output is:
32 *
33 * number: factor1 factor1 factor2 factor3 factor3 factor3 ...
34 *
35 * where factor1 < factor2 < factor3 < ...
36 *
37 * If no args are given, the list of numbers are read from stdin.
38 */
39
40 #include <err.h>
41 #include <ctype.h>
42 #include <errno.h>
43 #include <limits.h>
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <unistd.h>
47
48 #include "primes.h"
49
50 /*
51 * prime[i] is the (i-1)th prime.
52 *
53 * We are able to sieve 2^32-1 because this byte table yields all primes
54 * up to 65537 and 65537^2 > 2^32-1.
55 */
56 extern ubig prime[];
57 extern ubig *pr_limit; /* largest prime in the prime array */
58
59 void pr_fact __P((ubig)); /* print factors of a value */
60 void usage __P((void));
61
62 int
main(argc,argv)63 main(argc, argv)
64 int argc;
65 char *argv[];
66 {
67 ubig val;
68 int ch;
69 char *p, buf[100]; /* > max number of digits. */
70
71 while ((ch = getopt(argc, argv, "")) != EOF)
72 switch (ch) {
73 case '?':
74 default:
75 usage();
76 }
77 argc -= optind;
78 argv += optind;
79
80 /* No args supplied, read numbers from stdin. */
81 if (argc == 0)
82 for (;;) {
83 if (fgets(buf, sizeof(buf), stdin) == NULL) {
84 if (ferror(stdin))
85 err(1, "stdin");
86 exit (0);
87 }
88 for (p = buf; isblank(*p); ++p);
89 if (*p == '\n' || *p == '\0')
90 continue;
91 if (*p == '-')
92 errx(1, "negative numbers aren't permitted.");
93 errno = 0;
94 val = strtoul(buf, &p, 10);
95 if (errno)
96 err(1, "%s", buf);
97 if (*p != '\n')
98 errx(1, "%s: illegal numeric format.", buf);
99 pr_fact(val);
100 }
101 /* Factor the arguments. */
102 else
103 for (; *argv != NULL; ++argv) {
104 if (argv[0][0] == '-')
105 errx(1, "negative numbers aren't permitted.");
106 errno = 0;
107 val = strtoul(argv[0], &p, 10);
108 if (errno)
109 err(1, "%s", argv[0]);
110 if (*p != '\0')
111 errx(1, "%s: illegal numeric format.", argv[0]);
112 pr_fact(val);
113 }
114 exit(0);
115 }
116
117 /*
118 * pr_fact - print the factors of a number
119 *
120 * If the number is 0 or 1, then print the number and return.
121 * If the number is < 0, print -1, negate the number and continue
122 * processing.
123 *
124 * Print the factors of the number, from the lowest to the highest.
125 * A factor will be printed numtiple times if it divides the value
126 * multiple times.
127 *
128 * Factors are printed with leading tabs.
129 */
130 void
pr_fact(val)131 pr_fact(val)
132 ubig val; /* Factor this value. */
133 {
134 ubig *fact; /* The factor found. */
135
136 /* Firewall - catch 0 and 1. */
137 if (val == 0) /* Historical practice; 0 just exits. */
138 exit(0);
139 if (val == 1) {
140 (void)printf("1: 1\n");
141 return;
142 }
143
144 /* Factor value. */
145 (void)printf("%lu:", val);
146 for (fact = &prime[0]; val > 1; ++fact) {
147 /* Look for the smallest factor. */
148 do {
149 if (val % (long)*fact == 0)
150 break;
151 } while (++fact <= pr_limit);
152
153 /* Watch for primes larger than the table. */
154 if (fact > pr_limit) {
155 (void)printf(" %lu", val);
156 break;
157 }
158
159 /* Divide factor out until none are left. */
160 do {
161 (void)printf(" %lu", *fact);
162 val /= (long)*fact;
163 } while ((val % (long)*fact) == 0);
164
165 /* Let the user know we're doing something. */
166 (void)fflush(stdout);
167 }
168 (void)putchar('\n');
169 }
170
171 void
usage()172 usage()
173 {
174 (void)fprintf(stderr, "usage: factor [value ...]\n");
175 exit (0);
176 }
177