![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to factor.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / games / factor|
Return to factor.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / games / factor |
1.1 root 1: /*
2: * Copyright (c) 1989 The Regents of the University of California.
3: * 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 are permitted
9: * provided that: (1) source distributions retain this entire copyright
10: * notice and comment, and (2) distributions including binaries display
11: * the following acknowledgement: ``This product includes software
12: * developed by the University of California, Berkeley and its contributors''
13: * in the documentation or other materials provided with the distribution
14: * and in all advertising materials mentioning features or use of this
15: * software. Neither the name of the University nor the names of its
16: * contributors may be used to endorse or promote products derived
17: * from this software without specific prior written permission.
18: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
19: * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
20: * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
21: */
22:
23: #ifndef lint
24: char copyright[] =
25: "@(#) Copyright (c) 1989 The Regents of the University of California.\n\
26: All rights reserved.\n";
27: #endif /* not lint */
28:
29: #ifndef lint
30: static char sccsid[] = "@(#)factor.c 4.4 (Berkeley) 6/1/90";
31: #endif /* not lint */
32:
33: /*
34: * factor - factor a number into primes
35: *
36: * By: Landon Curt Noll [email protected], ...!{sun,tolsoft}!hoptoad!chongo
37: *
38: * chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
39: *
40: * usage:
41: * factor [number] ...
42: *
43: * The form of the output is:
44: *
45: * number: factor1 factor1 factor2 factor3 factor3 factor3 ...
46: *
47: * where factor1 < factor2 < factor3 < ...
48: *
49: * If no args are given, the list of numbers are read from stdin.
50: */
51:
52: #include <stdio.h>
53: #include <ctype.h>
54: #include "primes.h"
55:
56: /*
57: * prime[i] is the (i-1)th prime.
58: *
59: * We are able to sieve 2^32-1 because this byte table yields all primes
60: * up to 65537 and 65537^2 > 2^32-1.
61: */
62: extern ubig prime[];
63: extern ubig *pr_limit; /* largest prime in the prime array */
64:
65: #define MAX_LINE 255 /* max line allowed on stdin */
66:
67: void pr_fact(); /* print factors of a value */
68: long small_fact(); /* find smallest factor of a value */
69: char *read_num_buf(); /* read a number buffer */
70: char *program; /* name of this program */
71:
72: main(argc, argv)
73: int argc; /* arg count */
74: char *argv[]; /* the args */
75: {
76: int arg; /* which arg to factor */
77: long val; /* the value to factor */
78: char buf[MAX_LINE+1]; /* input buffer */
79:
80: /* parse args */
81: program = argv[0];
82: if (argc >= 2) {
83:
84: /* factor each arg */
85: for (arg=1; arg < argc; ++arg) {
86:
87: /* process the buffer */
88: if (read_num_buf(NULL, argv[arg]) == NULL) {
89: fprintf(stderr, "%s: ouch\n", program);
90: exit(1);
91: }
92:
93: /* factor the argument */
94: if (sscanf(argv[arg], "%ld", &val) == 1) {
95: pr_fact(val);
96: } else {
97: fprintf(stderr, "%s: ouch\n", program);
98: exit(1);
99: }
100: }
101:
102: /* no args supplied, read numbers from stdin */
103: } else {
104: /*
105: * read asciii numbers from input
106: */
107: while (read_num_buf(stdin, buf) != NULL) {
108:
109: /* factor the argument */
110: if (sscanf(buf, "%ld", &val) == 1) {
111: pr_fact(val);
112: }
113: }
114: }
115: exit(0);
116: }
117:
118: /*
119: * read_num_buf - read a number buffer from a stream
120: *
121: * Read a number on a line of the form:
122: *
123: * ^[ \t]*\([+-]?[0-9][0-9]\)*.*$
124: *
125: * where ? is a 1-or-0 operator and the number is within \( \).
126: *
127: * If does not match the above pattern, it is ignored and a new
128: * line is read. If the number is too large or small, we will
129: * print ouch and read a new line.
130: *
131: * We have to be very careful on how we check the magnitude of the
132: * input. We can not use numeric checks because of the need to
133: * check values against maximum numeric values.
134: *
135: * This routine will return a line containing a ascii number between
136: * NEG_SEMIBIG and SEMIBIG, or it will return NULL.
137: *
138: * If the stream is NULL then buf will be processed as if were
139: * a single line stream.
140: *
141: * returns:
142: * char * pointer to leading digit, + or -
143: * NULL EOF or error
144: */
145: char *
146: read_num_buf(input, buf)
147: FILE *input; /* input stream or NULL */
148: char *buf; /* input buffer */
149: {
150: static char limit[MAX_LINE+1]; /* ascii value of SEMIBIG */
151: static int limit_len; /* digit count of limit */
152: static char neg_limit[MAX_LINE+1]; /* value of NEG_SEMIBIG */
153: static int neg_limit_len; /* digit count of neg_limit */
154: int len; /* digits in input (excluding +/-) */
155: char *s; /* line start marker */
156: char *d; /* first digit, skip +/- */
157: char *p; /* scan pointer */
158: char *z; /* zero scan pointer */
159:
160: /* form the ascii value of SEMIBIG if needed */
161: if (!isascii(limit[0]) || !isdigit(limit[0])) {
162: sprintf(limit, "%ld", SEMIBIG);
163: limit_len = strlen(limit);
164: sprintf(neg_limit, "%ld", NEG_SEMIBIG);
165: neg_limit_len = strlen(neg_limit)-1; /* exclude - */
166: }
167:
168: /*
169: * the search for a good line
170: */
171: if (input != NULL && fgets(buf, MAX_LINE, input) == NULL) {
172: /* error or EOF */
173: return NULL;
174: }
175: do {
176:
177: /* ignore leading whitespace */
178: for (s=buf; *s && s < buf+MAX_LINE; ++s) {
179: if (!isascii(*s) || !isspace(*s)) {
180: break;
181: }
182: }
183:
184: /* skip over any leading + or - */
185: if (*s == '+' || *s == '-') {
186: d = s+1;
187: } else {
188: d = s;
189: }
190:
191: /* note leading zeros */
192: for (z=d; *z && z < buf+MAX_LINE; ++z) {
193: if (*z != '0') {
194: break;
195: }
196: }
197:
198: /* scan for the first non-digit */
199: for (p=d; *p && p < buf+MAX_LINE; ++p) {
200: if (!isascii(*p) || !isdigit(*p)) {
201: break;
202: }
203: }
204:
205: /* ignore empty lines */
206: if (p == d) {
207: continue;
208: }
209: *p = '\0';
210:
211: /* object if too many digits */
212: len = strlen(z);
213: len = (len<=0) ? 1 : len;
214: if (*s == '-') {
215: /* accept if digit count is below limit */
216: if (len < neg_limit_len) {
217: /* we have good input */
218: return s;
219:
220: /* reject very large numbers */
221: } else if (len > neg_limit_len) {
222: fprintf(stderr, "%s: ouch\n", program);
223: exit(1);
224:
225: /* carefully check against near limit numbers */
226: } else if (strcmp(z, neg_limit+1) > 0) {
227: fprintf(stderr, "%s: ouch\n", program);
228: exit(1);
229: }
230: /* number is near limit, but is under it */
231: return s;
232:
233: } else {
234: /* accept if digit count is below limit */
235: if (len < limit_len) {
236: /* we have good input */
237: return s;
238:
239: /* reject very large numbers */
240: } else if (len > limit_len) {
241: fprintf(stderr, "%s: ouch\n", program);
242: exit(1);
243:
244: /* carefully check against near limit numbers */
245: } else if (strcmp(z, limit) > 0) {
246: fprintf(stderr, "%s: ouch\n", program);
247: exit(1);
248: }
249: /* number is near limit, but is under it */
250: return s;
251: }
252: } while (input != NULL && fgets(buf, MAX_LINE, input) != NULL);
253:
254: /* error or EOF */
255: return NULL;
256: }
257:
258:
259: /*
260: * pr_fact - print the factors of a number
261: *
262: * If the number is 0 or 1, then print the number and return.
263: * If the number is < 0, print -1, negate the number and continue
264: * processing.
265: *
266: * Print the factors of the number, from the lowest to the highest.
267: * A factor will be printed numtiple times if it divides the value
268: * multiple times.
269: *
270: * Factors are printed with leading tabs.
271: */
272: void
273: pr_fact(val)
274: long val; /* factor this value */
275: {
276: ubig *fact; /* the factor found */
277:
278: /* firewall - catch 0 and 1 */
279: switch (val) {
280: case -2147483648:
281: /* avoid negation problems */
282: puts("-2147483648: -1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2\n");
283: return;
284: case -1:
285: puts("-1: -1\n");
286: return;
287: case 0:
288: exit(0);
289: case 1:
290: puts("1: 1\n");
291: return;
292: default:
293: if (val < 0) {
294: val = -val;
295: printf("%ld: -1", val);
296: } else {
297: printf("%ld:", val);
298: }
299: fflush(stdout);
300: break;
301: }
302:
303: /*
304: * factor value
305: */
306: fact = &prime[0];
307: while (val > 1) {
308:
309: /* look for the smallest factor */
310: do {
311: if (val%(long)*fact == 0) {
312: break;
313: }
314: } while (++fact <= pr_limit);
315:
316: /* watch for primes larger than the table */
317: if (fact > pr_limit) {
318: printf(" %ld\n", val);
319: return;
320: }
321:
322: /* divide factor out until none are left */
323: do {
324: printf(" %ld", *fact);
325: val /= (long)*fact;
326: } while ((val % (long)*fact) == 0);
327: fflush(stdout);
328: ++fact;
329: }
330: putchar('\n');
331: return;
332: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.