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 * %sccs.include.redist.c% 9 */ 10 11 #ifndef lint 12 char copyright[] = 13 "@(#) Copyright (c) 1989 The Regents of the University of California.\n\ 14 All rights reserved.\n"; 15 #endif /* not lint */ 16 17 #ifndef lint 18 static char sccsid[] = "@(#)factor.c 4.4 (Berkeley) 06/01/90"; 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 <stdio.h> 41 #include <ctype.h> 42 #include "primes.h" 43 44 /* 45 * prime[i] is the (i-1)th prime. 46 * 47 * We are able to sieve 2^32-1 because this byte table yields all primes 48 * up to 65537 and 65537^2 > 2^32-1. 49 */ 50 extern ubig prime[]; 51 extern ubig *pr_limit; /* largest prime in the prime array */ 52 53 #define MAX_LINE 255 /* max line allowed on stdin */ 54 55 void pr_fact(); /* print factors of a value */ 56 long small_fact(); /* find smallest factor of a value */ 57 char *read_num_buf(); /* read a number buffer */ 58 char *program; /* name of this program */ 59 60 main(argc, argv) 61 int argc; /* arg count */ 62 char *argv[]; /* the args */ 63 { 64 int arg; /* which arg to factor */ 65 long val; /* the value to factor */ 66 char buf[MAX_LINE+1]; /* input buffer */ 67 68 /* parse args */ 69 program = argv[0]; 70 if (argc >= 2) { 71 72 /* factor each arg */ 73 for (arg=1; arg < argc; ++arg) { 74 75 /* process the buffer */ 76 if (read_num_buf(NULL, argv[arg]) == NULL) { 77 fprintf(stderr, "%s: ouch\n", program); 78 exit(1); 79 } 80 81 /* factor the argument */ 82 if (sscanf(argv[arg], "%ld", &val) == 1) { 83 pr_fact(val); 84 } else { 85 fprintf(stderr, "%s: ouch\n", program); 86 exit(1); 87 } 88 } 89 90 /* no args supplied, read numbers from stdin */ 91 } else { 92 /* 93 * read asciii numbers from input 94 */ 95 while (read_num_buf(stdin, buf) != NULL) { 96 97 /* factor the argument */ 98 if (sscanf(buf, "%ld", &val) == 1) { 99 pr_fact(val); 100 } 101 } 102 } 103 exit(0); 104 } 105 106 /* 107 * read_num_buf - read a number buffer from a stream 108 * 109 * Read a number on a line of the form: 110 * 111 * ^[ \t]*\([+-]?[0-9][0-9]\)*.*$ 112 * 113 * where ? is a 1-or-0 operator and the number is within \( \). 114 * 115 * If does not match the above pattern, it is ignored and a new 116 * line is read. If the number is too large or small, we will 117 * print ouch and read a new line. 118 * 119 * We have to be very careful on how we check the magnitude of the 120 * input. We can not use numeric checks because of the need to 121 * check values against maximum numeric values. 122 * 123 * This routine will return a line containing a ascii number between 124 * NEG_SEMIBIG and SEMIBIG, or it will return NULL. 125 * 126 * If the stream is NULL then buf will be processed as if were 127 * a single line stream. 128 * 129 * returns: 130 * char * pointer to leading digit, + or - 131 * NULL EOF or error 132 */ 133 char * 134 read_num_buf(input, buf) 135 FILE *input; /* input stream or NULL */ 136 char *buf; /* input buffer */ 137 { 138 static char limit[MAX_LINE+1]; /* ascii value of SEMIBIG */ 139 static int limit_len; /* digit count of limit */ 140 static char neg_limit[MAX_LINE+1]; /* value of NEG_SEMIBIG */ 141 static int neg_limit_len; /* digit count of neg_limit */ 142 int len; /* digits in input (excluding +/-) */ 143 char *s; /* line start marker */ 144 char *d; /* first digit, skip +/- */ 145 char *p; /* scan pointer */ 146 char *z; /* zero scan pointer */ 147 148 /* form the ascii value of SEMIBIG if needed */ 149 if (!isascii(limit[0]) || !isdigit(limit[0])) { 150 sprintf(limit, "%ld", SEMIBIG); 151 limit_len = strlen(limit); 152 sprintf(neg_limit, "%ld", NEG_SEMIBIG); 153 neg_limit_len = strlen(neg_limit)-1; /* exclude - */ 154 } 155 156 /* 157 * the search for a good line 158 */ 159 if (input != NULL && fgets(buf, MAX_LINE, input) == NULL) { 160 /* error or EOF */ 161 return NULL; 162 } 163 do { 164 165 /* ignore leading whitespace */ 166 for (s=buf; *s && s < buf+MAX_LINE; ++s) { 167 if (!isascii(*s) || !isspace(*s)) { 168 break; 169 } 170 } 171 172 /* skip over any leading + or - */ 173 if (*s == '+' || *s == '-') { 174 d = s+1; 175 } else { 176 d = s; 177 } 178 179 /* note leading zeros */ 180 for (z=d; *z && z < buf+MAX_LINE; ++z) { 181 if (*z != '0') { 182 break; 183 } 184 } 185 186 /* scan for the first non-digit */ 187 for (p=d; *p && p < buf+MAX_LINE; ++p) { 188 if (!isascii(*p) || !isdigit(*p)) { 189 break; 190 } 191 } 192 193 /* ignore empty lines */ 194 if (p == d) { 195 continue; 196 } 197 *p = '\0'; 198 199 /* object if too many digits */ 200 len = strlen(z); 201 len = (len<=0) ? 1 : len; 202 if (*s == '-') { 203 /* accept if digit count is below limit */ 204 if (len < neg_limit_len) { 205 /* we have good input */ 206 return s; 207 208 /* reject very large numbers */ 209 } else if (len > neg_limit_len) { 210 fprintf(stderr, "%s: ouch\n", program); 211 exit(1); 212 213 /* carefully check against near limit numbers */ 214 } else if (strcmp(z, neg_limit+1) > 0) { 215 fprintf(stderr, "%s: ouch\n", program); 216 exit(1); 217 } 218 /* number is near limit, but is under it */ 219 return s; 220 221 } else { 222 /* accept if digit count is below limit */ 223 if (len < limit_len) { 224 /* we have good input */ 225 return s; 226 227 /* reject very large numbers */ 228 } else if (len > limit_len) { 229 fprintf(stderr, "%s: ouch\n", program); 230 exit(1); 231 232 /* carefully check against near limit numbers */ 233 } else if (strcmp(z, limit) > 0) { 234 fprintf(stderr, "%s: ouch\n", program); 235 exit(1); 236 } 237 /* number is near limit, but is under it */ 238 return s; 239 } 240 } while (input != NULL && fgets(buf, MAX_LINE, input) != NULL); 241 242 /* error or EOF */ 243 return NULL; 244 } 245 246 247 /* 248 * pr_fact - print the factors of a number 249 * 250 * If the number is 0 or 1, then print the number and return. 251 * If the number is < 0, print -1, negate the number and continue 252 * processing. 253 * 254 * Print the factors of the number, from the lowest to the highest. 255 * A factor will be printed numtiple times if it divides the value 256 * multiple times. 257 * 258 * Factors are printed with leading tabs. 259 */ 260 void 261 pr_fact(val) 262 long val; /* factor this value */ 263 { 264 ubig *fact; /* the factor found */ 265 266 /* firewall - catch 0 and 1 */ 267 switch (val) { 268 case -2147483648: 269 /* avoid negation problems */ 270 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"); 271 return; 272 case -1: 273 puts("-1: -1\n"); 274 return; 275 case 0: 276 exit(0); 277 case 1: 278 puts("1: 1\n"); 279 return; 280 default: 281 if (val < 0) { 282 val = -val; 283 printf("%ld: -1", val); 284 } else { 285 printf("%ld:", val); 286 } 287 fflush(stdout); 288 break; 289 } 290 291 /* 292 * factor value 293 */ 294 fact = &prime[0]; 295 while (val > 1) { 296 297 /* look for the smallest factor */ 298 do { 299 if (val%(long)*fact == 0) { 300 break; 301 } 302 } while (++fact <= pr_limit); 303 304 /* watch for primes larger than the table */ 305 if (fact > pr_limit) { 306 printf(" %ld\n", val); 307 return; 308 } 309 310 /* divide factor out until none are left */ 311 do { 312 printf(" %ld", *fact); 313 val /= (long)*fact; 314 } while ((val % (long)*fact) == 0); 315 fflush(stdout); 316 ++fact; 317 } 318 putchar('\n'); 319 return; 320 } 321