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