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