Home | History | Annotate | Line # | Download | only in sysinst
factor.c revision 1.1.6.2 
      1 /*	$NetBSD: factor.c,v 1.1.6.2 2014/08/20 00:05:13 tls 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