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