factor.c revision 42338
12490Sjkh/* 22490Sjkh * Copyright (c) 1989, 1993 32490Sjkh * The Regents of the University of California. All rights reserved. 42490Sjkh * 52490Sjkh * This code is derived from software contributed to Berkeley by 62490Sjkh * Landon Curt Noll. 72490Sjkh * 82490Sjkh * Redistribution and use in source and binary forms, with or without 92490Sjkh * modification, are permitted provided that the following conditions 102490Sjkh * are met: 112490Sjkh * 1. Redistributions of source code must retain the above copyright 122490Sjkh * notice, this list of conditions and the following disclaimer. 132490Sjkh * 2. Redistributions in binary form must reproduce the above copyright 142490Sjkh * notice, this list of conditions and the following disclaimer in the 152490Sjkh * documentation and/or other materials provided with the distribution. 162490Sjkh * 3. All advertising materials mentioning features or use of this software 172490Sjkh * must display the following acknowledgement: 182490Sjkh * This product includes software developed by the University of 192490Sjkh * California, Berkeley and its contributors. 202490Sjkh * 4. Neither the name of the University nor the names of its contributors 212490Sjkh * may be used to endorse or promote products derived from this software 222490Sjkh * without specific prior written permission. 232490Sjkh * 242490Sjkh * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 252490Sjkh * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 262490Sjkh * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 272490Sjkh * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 282490Sjkh * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 292490Sjkh * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 302490Sjkh * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 312490Sjkh * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 322490Sjkh * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 332490Sjkh * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 342490Sjkh * SUCH DAMAGE. 352490Sjkh */ 362490Sjkh 372490Sjkh#ifndef lint 382490Sjkhstatic char copyright[] = 392490Sjkh"@(#) Copyright (c) 1989, 1993\n\ 402490Sjkh The Regents of the University of California. All rights reserved.\n"; 412490Sjkh#endif /* not lint */ 422490Sjkh 432490Sjkh#ifndef lint 4423726Speterstatic char sccsid[] = "@(#)factor.c 8.4 (Berkeley) 5/4/95"; 452490Sjkh#endif /* not lint */ 462490Sjkh 472490Sjkh/* 482490Sjkh * factor - factor a number into primes 492490Sjkh * 502490Sjkh * By: Landon Curt Noll chongo@toad.com, ...!{sun,tolsoft}!hoptoad!chongo 512490Sjkh * 522490Sjkh * chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\ 532490Sjkh * 542490Sjkh * usage: 552490Sjkh * factor [number] ... 562490Sjkh * 572490Sjkh * The form of the output is: 582490Sjkh * 592490Sjkh * number: factor1 factor1 factor2 factor3 factor3 factor3 ... 602490Sjkh * 612490Sjkh * where factor1 < factor2 < factor3 < ... 622490Sjkh * 632490Sjkh * If no args are given, the list of numbers are read from stdin. 642490Sjkh */ 652490Sjkh 662490Sjkh#include <err.h> 672490Sjkh#include <ctype.h> 682490Sjkh#include <errno.h> 692490Sjkh#include <limits.h> 702490Sjkh#include <stdio.h> 712490Sjkh#include <stdlib.h> 7223726Speter#include <unistd.h> 732490Sjkh 742490Sjkh#include "primes.h" 752490Sjkh 762490Sjkh/* 772490Sjkh * prime[i] is the (i-1)th prime. 782490Sjkh * 798856Srgrimes * We are able to sieve 2^32-1 because this byte table yields all primes 802490Sjkh * up to 65537 and 65537^2 > 2^32-1. 812490Sjkh */ 822490Sjkhextern ubig prime[]; 832490Sjkhextern ubig *pr_limit; /* largest prime in the prime array */ 842490Sjkh 8542338Simpint hflag; 8642338Simp 872490Sjkhvoid pr_fact __P((ubig)); /* print factors of a value */ 882490Sjkhvoid usage __P((void)); 892490Sjkh 902490Sjkhint 912490Sjkhmain(argc, argv) 922490Sjkh int argc; 932490Sjkh char *argv[]; 942490Sjkh{ 952490Sjkh ubig val; 962490Sjkh int ch; 972490Sjkh char *p, buf[100]; /* > max number of digits. */ 982490Sjkh 9942338Simp while ((ch = getopt(argc, argv, "h")) != -1) 1002490Sjkh switch (ch) { 10142338Simp case 'h': 10242338Simp hflag++; 10342338Simp break; 1042490Sjkh case '?': 1052490Sjkh default: 1062490Sjkh usage(); 1072490Sjkh } 1082490Sjkh argc -= optind; 1092490Sjkh argv += optind; 1102490Sjkh 1112490Sjkh /* No args supplied, read numbers from stdin. */ 1122490Sjkh if (argc == 0) 1132490Sjkh for (;;) { 1142490Sjkh if (fgets(buf, sizeof(buf), stdin) == NULL) { 1152490Sjkh if (ferror(stdin)) 1162490Sjkh err(1, "stdin"); 1172490Sjkh exit (0); 1182490Sjkh } 1192490Sjkh for (p = buf; isblank(*p); ++p); 1202490Sjkh if (*p == '\n' || *p == '\0') 1212490Sjkh continue; 1222490Sjkh if (*p == '-') 1232490Sjkh errx(1, "negative numbers aren't permitted."); 1242490Sjkh errno = 0; 12542338Simp val = strtoul(buf, &p, 0); 1262490Sjkh if (errno) 1272490Sjkh err(1, "%s", buf); 1282490Sjkh if (*p != '\n') 1292490Sjkh errx(1, "%s: illegal numeric format.", buf); 1302490Sjkh pr_fact(val); 1312490Sjkh } 1322490Sjkh /* Factor the arguments. */ 1332490Sjkh else 1342490Sjkh for (; *argv != NULL; ++argv) { 1352490Sjkh if (argv[0][0] == '-') 1362490Sjkh errx(1, "negative numbers aren't permitted."); 1372490Sjkh errno = 0; 13842338Simp val = strtoul(argv[0], &p, 0); 1392490Sjkh if (errno) 1402490Sjkh err(1, "%s", argv[0]); 1412490Sjkh if (*p != '\0') 1422490Sjkh errx(1, "%s: illegal numeric format.", argv[0]); 1432490Sjkh pr_fact(val); 1442490Sjkh } 1452490Sjkh exit(0); 1462490Sjkh} 1472490Sjkh 1482490Sjkh/* 1492490Sjkh * pr_fact - print the factors of a number 1502490Sjkh * 1512490Sjkh * If the number is 0 or 1, then print the number and return. 1522490Sjkh * If the number is < 0, print -1, negate the number and continue 1532490Sjkh * processing. 1542490Sjkh * 1552490Sjkh * Print the factors of the number, from the lowest to the highest. 1562490Sjkh * A factor will be printed numtiple times if it divides the value 1572490Sjkh * multiple times. 1582490Sjkh * 1592490Sjkh * Factors are printed with leading tabs. 1602490Sjkh */ 1612490Sjkhvoid 1622490Sjkhpr_fact(val) 1632490Sjkh ubig val; /* Factor this value. */ 1642490Sjkh{ 1652490Sjkh ubig *fact; /* The factor found. */ 1662490Sjkh 1672490Sjkh /* Firewall - catch 0 and 1. */ 1682490Sjkh if (val == 0) /* Historical practice; 0 just exits. */ 1692490Sjkh exit(0); 1702490Sjkh if (val == 1) { 1712490Sjkh (void)printf("1: 1\n"); 1722490Sjkh return; 1732490Sjkh } 1742490Sjkh 1752490Sjkh /* Factor value. */ 17642338Simp (void)printf(hflag ? "0x%x:" : "%lu:", val); 1772490Sjkh for (fact = &prime[0]; val > 1; ++fact) { 1782490Sjkh /* Look for the smallest factor. */ 1792490Sjkh do { 1802490Sjkh if (val % (long)*fact == 0) 1812490Sjkh break; 1822490Sjkh } while (++fact <= pr_limit); 1832490Sjkh 1842490Sjkh /* Watch for primes larger than the table. */ 1852490Sjkh if (fact > pr_limit) { 18642338Simp (void)printf(hflag ? " 0x%x" : " %lu", val); 1872490Sjkh break; 1882490Sjkh } 1892490Sjkh 1902490Sjkh /* Divide factor out until none are left. */ 1912490Sjkh do { 19242338Simp (void)printf(hflag ? " 0x%x" : " %lu", *fact); 1932490Sjkh val /= (long)*fact; 1942490Sjkh } while ((val % (long)*fact) == 0); 1952490Sjkh 1962490Sjkh /* Let the user know we're doing something. */ 1972490Sjkh (void)fflush(stdout); 1982490Sjkh } 1992490Sjkh (void)putchar('\n'); 2002490Sjkh} 2012490Sjkh 2022490Sjkhvoid 2032490Sjkhusage() 2042490Sjkh{ 20542338Simp (void)fprintf(stderr, "usage: factor -h [value ...]\n"); 2062490Sjkh exit (0); 2072490Sjkh} 208