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.2 (Berkeley) 03/21/94"; 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 47 #include "primes.h" 48 49 /* 50 * prime[i] is the (i-1)th prime. 51 * 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. 54 */ 55 extern ubig prime[]; 56 extern ubig *pr_limit; /* largest prime in the prime array */ 57 58 void pr_fact __P((ubig)); /* print factors of a value */ 59 void usage __P((void)); 60 61 int 62 main(argc, argv) 63 int argc; 64 char *argv[]; 65 { 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(); 75 } 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); 86 } 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); 99 } 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); 112 } 113 exit(0); 114 } 115 116 /* 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. 126 * 127 * Factors are printed with leading tabs. 128 */ 129 void 130 pr_fact(val) 131 ubig val; /* Factor this value. */ 132 { 133 ubig *fact; /* The factor found. */ 134 135 /* Firewall - catch 0 and 1. */ 136 if (val == 0) /* Historical practice; 0 just exits. */ 137 exit(0); 138 if (val == 1) { 139 (void)printf("1: 1\n"); 140 return; 141 } 142 143 /* Factor value. */ 144 (void)printf("%ld:", val); 145 for (fact = &prime[0]; val > 1; ++fact) { 146 /* Look for the smallest factor. */ 147 do { 148 if (val % (long)*fact == 0) 149 break; 150 } while (++fact <= pr_limit); 151 152 /* Watch for primes larger than the table. */ 153 if (fact > pr_limit) { 154 (void)printf(" %ld", val); 155 break; 156 } 157 158 /* Divide factor out until none are left. */ 159 do { 160 (void)printf(" %ld", *fact); 161 val /= (long)*fact; 162 } while ((val % (long)*fact) == 0); 163 164 /* Let the user know we're doing something. */ 165 (void)fflush(stdout); 166 } 167 (void)putchar('\n'); 168 } 169 170 void 171 usage() 172 { 173 (void)fprintf(stderr, "usage: factor [value ...]\n"); 174 exit (0); 175 } 176