1 /* $NetBSD: factor.c,v 1.1 2014/07/26 19:30:44 dholland Exp $ */ 2 3 /* 4 * Copyright 1997 Piermont Information Systems Inc. 5 * All rights reserved. 6 * 7 * Written by Philip A. Nelson for Piermont Information Systems Inc. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 3. The name of Piermont Information Systems Inc. may not be used to endorse 18 * or promote products derived from this software without specific prior 19 * written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY PIERMONT INFORMATION SYSTEMS INC. ``AS IS'' 22 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL PIERMONT INFORMATION SYSTEMS INC. BE 25 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 28 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 29 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 30 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 31 * THE POSSIBILITY OF SUCH DAMAGE. 32 * 33 */ 34 35 /* Prototypes for strict prototyping. */ 36 37 #include <sys/cdefs.h> 38 39 #include <stdio.h> 40 41 42 /* 43 * primes - prime table, built to include up to 46345 because 44 * sqrt(2^31) = 46340.9500118415 45 * 46 * building the table instead of storing a precomputed table saves 47 * about 19K of space on the binary image. 48 */ 49 50 #ifdef TESTING 51 long primes[4800]; 52 int num_primes = 2; 53 54 static void build_primes (long max); 55 void factor (long val, long *fact_list, int fact_size, int *num_fact); 56 57 static void 58 build_primes(max) 59 long max; 60 { 61 long pc; 62 int j; 63 long rem; 64 65 /* 66 * Initialise primes at run-time rather than compile time 67 * so it's put in bss rather than data. 68 */ 69 primes[0] = 2; 70 primes[1] = 3; 71 72 for (pc = primes[num_primes-1]; pc < 46345 && pc*pc <= max; pc+=2) { 73 j = 0; 74 rem = 1; 75 while (j < num_primes && primes[j] * primes[j] <= pc) { 76 if ((rem = pc % primes[j]) == 0) 77 break; 78 j++; 79 } 80 if (rem) 81 primes[num_primes++] = pc; 82 } 83 } 84 85 /* factor: prepare a list of prime factors of val. 86 The last number may not be a prime factor is the list is not 87 long enough. */ 88 89 void 90 factor(val, fact_list, fact_size, num_fact) 91 long val; 92 long *fact_list; 93 int fact_size; 94 int *num_fact; 95 { 96 int i; 97 98 /* Check to make sure we have enough primes. */ 99 build_primes(val); 100 101 i = 0; 102 *num_fact = 0; 103 while (*num_fact < fact_size-1 && val > 1 && i < num_primes) { 104 /* Find the next prime that divides. */ 105 while (i < num_primes && val % primes[i] != 0) i++; 106 107 /* Put factors in array. */ 108 while (*num_fact < fact_size-1 && i < num_primes && 109 val % primes[i] == 0) { 110 fact_list[(*num_fact)++] = primes[i]; 111 val /= primes[i]; 112 } 113 } 114 if (val > 1) 115 fact_list[(*num_fact)++] = val; 116 } 117 118 119 120 #include <stdio.h> 121 #include <stdlib.h> 122 123 int 124 main(int argc, char **argv) 125 { 126 long facts[30]; 127 long val; 128 int i, nfact; 129 int arg; 130 131 if (argc < 2) { 132 fprintf (stderr, "usage: %s numbers\n", argv[0]); 133 exit(1); 134 } 135 136 /* Factor each arg! */ 137 for (arg = 1; arg < argc; arg++) { 138 139 val = atol(argv[arg]); 140 factor (val, facts, 30, &nfact); 141 142 printf ("%ld:", val); 143 for (i = 0; i<nfact; i++) 144 printf (" %ld", facts[i]); 145 printf ("\n"); 146 147 } 148 149 return 0; 150 } 151 #endif 152