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