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