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