// 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();
}
}