Home | History | Annotate | Line # | Download | only in sysinst
factor.c revision 1.2 
      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
     48 long primes[4800];
     49 int  num_primes = 2;
     50 
     51 static void build_primes (long max);
     52 void factor (long val, long *fact_list, int fact_size, int *num_fact);
     53 
     54 static void
     55 build_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 
     85 void
     86 factor(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 
    115 int
    116 main(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