1/* $NetBSD: factor.c,v 1.2 2021/01/31 20:51:04 rillig 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#include <sys/cdefs.h> 36#include <stdio.h> 37 38 39/* 40 * primes - prime table, built to include up to 46345 because 41 * sqrt(2^31) = 46340.9500118415 42 * 43 * building the table instead of storing a precomputed table saves 44 * about 19K of space on the binary image. 45 */ 46 47#ifdef TESTING 48long primes[4800]; 49int num_primes = 2; 50 51static void build_primes (long max); 52void factor (long val, long *fact_list, int fact_size, int *num_fact); 53 54static void 55build_primes(long max) 56{ 57 long pc; 58 int j; 59 long rem; 60 61 /* 62 * Initialise primes at run-time rather than compile time 63 * so it's put in bss rather than data. 64 */ 65 primes[0] = 2; 66 primes[1] = 3; 67 68 for (pc = primes[num_primes-1]; pc < 46345 && pc*pc <= max; pc+=2) { 69 j = 0; 70 rem = 1; 71 while (j < num_primes && primes[j] * primes[j] <= pc) { 72 if ((rem = pc % primes[j]) == 0) 73 break; 74 j++; 75 } 76 if (rem) 77 primes[num_primes++] = pc; 78 } 79} 80 81/* factor: prepare a list of prime factors of val. 82 The last number may not be a prime factor if the list is not 83 long enough. */ 84 85void 86factor(long val, long *fact_list, int fact_size, int *num_fact) 87{ 88 int i; 89 90 /* Check to make sure we have enough primes. */ 91 build_primes(val); 92 93 i = 0; 94 *num_fact = 0; 95 while (*num_fact < fact_size-1 && val > 1 && i < num_primes) { 96 /* Find the next prime that divides. */ 97 while (i < num_primes && val % primes[i] != 0) i++; 98 99 /* Put factors in array. */ 100 while (*num_fact < fact_size-1 && i < num_primes && 101 val % primes[i] == 0) { 102 fact_list[(*num_fact)++] = primes[i]; 103 val /= primes[i]; 104 } 105 } 106 if (val > 1) 107 fact_list[(*num_fact)++] = val; 108} 109 110 111 112#include <stdio.h> 113#include <stdlib.h> 114 115int 116main(int argc, char **argv) 117{ 118 long facts[30]; 119 long val; 120 int i, nfact; 121 int arg; 122 123 if (argc < 2) { 124 fprintf (stderr, "usage: %s numbers\n", argv[0]); 125 exit(1); 126 } 127 128 /* Factor each arg! */ 129 for (arg = 1; arg < argc; arg++) { 130 131 val = atol(argv[arg]); 132 factor (val, facts, 30, &nfact); 133 134 printf ("%ld:", val); 135 for (i = 0; i<nfact; i++) 136 printf (" %ld", facts[i]); 137 printf ("\n"); 138 139 } 140 141 return 0; 142} 143#endif 144