Development Class C#

// Copyright 2008 Adrian Akison
// Distributed under license terms of CPOL http://www.rntsoft.com/info/cpol10.aspx
using System.Collections.Generic;
using System.Collections;
namespace CombinatorialCollections {
    /// 
    /// Utility class that maintains a small table of prime numbers and provides
    /// simple implementations of Prime Factorization algorithms.  
    /// This is a quick and dirty utility class to support calculations of permutation
    /// sets with indexes under 2^31.
    /// The prime table contains all primes up to Sqrt(2^31) which are all of the primes
    /// requires to factorize any Int32 positive integer.
    /// 

    public class SmallPrimeUtility {
        /// 
        /// Utility class, no instances allowed.
        /// 

        private SmallPrimeUtility() {
            ;
        }
        /// 
        /// Performs a prime factorization of a given integer using the table of primes in PrimeTable.
        /// Since this will only factor Int32 sized integers, a simple list of factors is returned instead
        /// of the more scalable, but more difficult to consume, list of primes and associated exponents.
        /// 

        /// The number to factorize, must be positive.
        /// A simple list of factors.
        public static List Factor(int i) {
            int primeIndex = 0;
            int prime = PrimeTable[primeIndex];
            List factors = new List();
            while(i > 1) {
                if(i % prime == 0) {
                    factors.Add(prime);
                    i /= prime;
                }
                else {
                    ++primeIndex;
                    prime = PrimeTable[primeIndex];
                }
            }
            return factors;
        }
        /// 
        /// Given two integers expressed as a list of prime factors, multiplies these numbers
        /// together and returns an integer also expressed as a set of prime factors.
        /// This allows multiplication to overflow well beyond a Int64 if necessary.  
        /// 

        /// Left Hand Side argument, expressed as list of prime factors.
        /// Right Hand Side argument, expressed as list of prime factors.
        /// Product, expressed as list of prime factors.
        public static List MultiplyPrimeFactors(IList lhs, IList rhs) {
            List product = new List();
            foreach(int prime in lhs) {
                product.Add(prime);
            }
            foreach(int prime in rhs) {
                product.Add(prime);
            }
            product.Sort();
            return product;
        }
        /// 
        /// Given two integers expressed as a list of prime factors, divides these numbers
        /// and returns an integer also expressed as a set of prime factors.
        /// If the result is not a integer, then the result is undefined.  That is, 11 / 5
        /// when divided by this function will not yield a correct result.
        /// As such, this function is ONLY useful for division with combinatorial results where 
        /// the result is known to be an integer AND the division occurs as the last operation(s).
        /// 

        /// Numerator argument, expressed as list of prime factors.
        /// Denominator argument, expressed as list of prime factors.
        /// Resultant, expressed as list of prime factors.
        public static List DividePrimeFactors(IList numerator, IList denominator) {
            List product = new List();
            foreach(int prime in numerator) {
                product.Add(prime);
            }
            foreach(int prime in denominator) {
                product.Remove(prime);
            }
            return product;
        }
        /// 
        /// Given a list of prime factors returns the long representation.
        /// 

        /// Integer, expressed as list of prime factors.
        /// Standard long representation.
        public static long EvaluatePrimeFactors(IList value) {
            long accumulator = 1;
            foreach(int prime in value) {
                accumulator *= prime;
            }
            return accumulator;
        }
        /// 
        /// Static initializer, set up prime table.
        /// 

        static SmallPrimeUtility() {
            CalculatePrimes();
        }
        /// 
        /// Calculate all primes up to Sqrt(2^32) = 2^16.  
        /// This table will be large enough for all factorizations for Int32's.
        /// Small tables are best built using the Sieve Of Eratosthenes,
        /// Reference: http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes
        /// 

        private static void CalculatePrimes() {
            // Build Sieve Of Eratosthenes
            BitArray sieve = new BitArray(65536, true);
            for(int possiblePrime = 2; possiblePrime <= 256; ++possiblePrime) {
                if(sieve[possiblePrime] == true) {
                    // It is prime, so remove all future factors...
                    for(int nonPrime = 2 * possiblePrime; nonPrime < 65536; nonPrime += possiblePrime) {
                        sieve[nonPrime] = false;
                    }
                }
            }
            // Scan sieve for primes...
            myPrimes = new List();
            for(int i = 2; i < 65536; ++i) {
                if(sieve[i] == true) {
                    myPrimes.Add(i);
                }
            }
        }
        /// 
        /// A List of all primes from 2 to 2^16.
        /// 

        public static IList PrimeTable {
            get {
                return myPrimes;
            }
        }
        private static List myPrimes = new List();
    }
}